Constructing strongly convex approximate hulls with inaccurate primitives

DOI10.1007/BF01190154zbMATH Open0797.68158OpenAlexW2050284373MaRDI QIDQ2366235FDOQ2366235

Authors: Leonidas 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

Recommendations

• Constructing strongly convex hulls using exact or rounded arithmetic
• Robust algorithms for constructing strongly convex hulls in parallel.
• Construction of the convex hull of a finite set of points when the computations are approximate
• A CONVEX HULL ALGORITHM FOR POINTS WITH APPROXIMATELY KNOWN POSITIONS
• Publication:4504027

zbMATH Keywords

computational geometryconvex hullrobust algorithmsapproximate computationsepsilon geometrystrongly convex polygons

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the Distribution of the Number of Admissible Points in a Vector Random Sample
• 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
• Title not available (Why is that?)

Cited In (23)

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

Uses Software

• BIGNUM

This page was built for publication: Constructing strongly convex approximate hulls with inaccurate primitives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366235)