Approximation algorithms for convex hulls

DOI10.1145/358315.358392zbMath0466.68059OpenAlexW2085121963MaRDI QIDQ3919102

Mark G. Faust, Jon Louis Bentley, Franco P. Preparata

Publication date: 1982

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/358315.358392

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Related Items

On the number of clusters ⋮ A new active convex hull model for image regions ⋮ Special cases of travelling salesman problems and heuristics ⋮ Approximating the diameter of a set of points in the Euclidean space ⋮ Approximating the discrete center line segment in linear time ⋮ Approximate Polytope Membership Queries ⋮ An efficient and numerically correct algorithm for the 2D convex hull problem ⋮ Approximate Convex Hull of Data Streams ⋮ Fast geometric approximation techniques and geometric embedding problems ⋮ On computing approximate convex hulls ⋮ A new variational approach based on level-set function for convex hull problem with outliers ⋮ An approximate algorithm for computing multidimensional convex hulls ⋮ Economical Delone Sets for Approximating Convex Bodies ⋮ A linear time algorithm for computing the convex hull of an ordered crossing polygon ⋮ A note on approximate convex hulls