NDLI: An efficient approach to removing geometric degeneracies

Please wait, while we are loading the content...

A subexponential bound for linear programming

A class of convex programs with applications to computational geometry

Linear optimization queries

Degenerate convex hulls in high dimensions without extra storage

Optimal parallel algorithms for triangulated simple polygons

Incremental topological flipping works for regular triangulations

An upper bound for conforming Delaunay triangulations

An optimal parallel algorithm for detecting weak visibility of a simple polygon

An efficient approach to removing geometric degeneracies

Numerical stability of algorithms for 2D Delaunay triangulations

Approximate decision algorithms for point set congruence

Measuring the resemblance of polygonal curves

On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane

Diameter, width, closest line pair, and parametric searching

Incidence and nearest-neighbor problems for lines in 3-space

Computing and verifying depth orders

Castles in the air revisited

Piercing convex sets

Computing the volume, counting integral points, and exponential sums

There is a universal topological plane

A linear-time algorithm for testing the inscribability of trivalent polyhedra

On Euclidean spanner graphs with small degree

New sparseness results on graph spanners

Coping with inconsistencies: a new approach to produce quality triangulations of polygonal domains with holes

Quality mesh generation in three dimensions

Triangulating polygons without large angles

Optical computational geometry

Stable placements for spider robots

A rational rotation method for robust geometric algorithms

A framework for dynamic graph drawing

How hard is halfspace range searching?

Range searching with efficient hierarchical cuttings

Ray shooting in convex polytopes

Minimum dissection of rectilinear polygon with arbitrary holes into rectangles

Intersection detection and separators for simple polygons

Manhattonian proximity in a simple polygon

Finding k farthest pairs and k closest/farthest bichromatic pairs for points in the plane

An optimal algorithm for the on-line closest-pair problem

On-line Steiner trees in the Euclidean plane

A priori inequalities for the Euclidean traveling salesman

Minkowski-type theorems and least-squares partitioning

Determining contractibility of curves

An efficient approach to removing geometric degeneracies

Content Provider	ACM Digital Library
Author	Emiris, Ioannis Canny, John
Abstract	Our aim is to perturb the input so that an algorithm designed under the hypothesis of input non-degeneracy can execute on arbitrary instances. The deterministic scheme of [EmCa] was the first efficient method and was applied to two important predicates. Here it is extended in a consistent manner to another two common predicates, thus making it valid for most algorithms in computational geometry. It is shown that this scheme incurs no extra algebraic complexity over the original algorithm while it increases the bit complexity by a factor roughly proportional to the dimension of the geometric space. The second contribution of this paper is a variant scheme for a restricted class of algorithms that is asymptotically optimal with respect to the algebraic as well as the bit complexity. Both methods are simple to implement and require no symbolic computation. They also conform to certain criteria ensuring that the solution to the original input can be restored from the output on the perturbed input. This is immediate when the input to solution mapping obeys a continuity property and requires some case-specific work otherwise. Finally we discuss extensions and limitations to our approach.
Starting Page	74
Ending Page	82
Page Count	9
File Format	PDF
ISBN	0897915178
DOI	10.1145/142675.142694
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1992-07-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in