On the complexity of finding the convex hull of a set of points
From MaRDI portal
Publication:1158971
DOI10.1016/0166-218X(82)90065-8zbMath0474.68081MaRDI QIDQ1158971
Publication date: 1982
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)
Related Items
A linear algorithm for finding the convex hull of a simple polygon, On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination, An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons, Comments on a lower bound for convex hull determination, How to reduce the average complexity of convex hull finding algorithms, Linear decision trees are too weak for convex hull problem, On the complexity of finding the convex hull of a set of points, On finding the convex hull of a simple polygon
Cites Work
- On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
- Comments on a lower bound for convex hull determination
- On the complexity of finding the convex hull of a set of points
- An efficient algorithm for determining the convex hull of a finite planar set
- A Lower Bound to Finding Convex Hulls
- On the complexity of computing the measure of ∪[a i ,b i ]
