On the complexity of finding the convex hull of a set of points

DOI10.1016/0166-218X(82)90065-8zbMath0474.68081MaRDI QIDQ1158971

David Avis

Publication date: 1982

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

linear decision tree algorithmsn log n lower bound

Mathematics Subject Classification ID

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 (8)

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 ]

This page was built for publication: On the complexity of finding the convex hull of a set of points