Constructing strongly convex approximate hulls with inaccurate primitives

DOI10.1007/BF01190154zbMath0797.68158OpenAlexW2050284373MaRDI QIDQ2366235

Leonidas J. Guibas, David H. Salesin, Jorge Stolfi

Publication date: 29 June 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01190154

zbMATH Keywords

convex hullcomputational geometryrobust algorithmsapproximate computationsepsilon geometrystrongly convex polygons

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

On detecting spatial regularity in noisy images ⋮ Largest and smallest convex hulls for imprecise points ⋮ Delaunay Triangulation of Imprecise Points Simplified and Extended ⋮ Voronoi Diagram and Delaunay Triangulation with Independent and Dependent Geometric Uncertainties ⋮ Three-dimensional unstructured mesh generation. III: Volume meshes ⋮ Convex hulls under uncertainty ⋮ Region-based approximation of probability distributions (for visibility between imprecise points among obstacles) ⋮ Half-plane point retrieval queries with independent and dependent geometric uncertainties ⋮ Largest convex hulls for constant size, convex-hull disjoint clusters ⋮ Minimizing the diameter of a spanning tree for imprecise points ⋮ Preprocessing imprecise points for Delaunay triangulation: simplified and extended ⋮ EXISTENCE AND COMPUTATION OF TOURS THROUGH IMPRECISE POINTS ⋮ Euclidean minimum spanning trees with independent and dependent geometric uncertainties ⋮ Constructing strongly convex hulls using exact or rounded arithmetic ⋮ Classroom examples of robustness problems in geometric computations ⋮ SMOOTHING IMPRECISE 1.5D TERRAINS ⋮ Largest bounding box, smallest diameter, and related problems on imprecise points ⋮ CONSTRUCTING A STRONGLY CONVEX SUPERHULL OF POINTS ⋮ Approximating Largest Convex Hulls for Imprecise Points ⋮ Approximating largest convex hulls for imprecise points ⋮ Delaunay triangulation of imprecise points in linear time after preprocessing ⋮ Robust algorithms for constructing strongly convex hulls in parallel. ⋮ Numerical stability of a convex hull algorithm for simple polygons ⋮ Structural tolerance and Delaunay triangulation

Uses Software

• BIGNUM

Cites Work

• Unnamed Item
• Unnamed Item
• Verifiable implementations of geometric algorithms using finite precision arithmetic
• Constructing strongly convex hulls using exact or rounded arithmetic
• Numerical stability of a convex hull algorithm for simple polygons
• On the Distribution of the Number of Admissible Points in a Vector Random Sample