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

DOI10.1016/0166-218X(82)90065-8MaRDI QIDQ1158971zbMATH OpenFDO

Authors 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) Discrete mathematics in relation to computer science (68R99) Convex sets in (2) dimensions (including convex curves) (52A10)

Cites work

• A Lower Bound to Finding Convex Hulls
• An efficient algorithm for determining the convex hull of a finite planar set
• Comments on a lower bound for convex hull determination
• On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
• On the complexity of computing the measure of ∪[a _i ,b _i ]
• On the complexity of finding the convex hull of a set of points

Cited in

(8)

• Linear decision trees are too weak for convex hull problem
• On finding the convex hull of a simple polygon
• A linear algorithm for finding the convex hull of a simple polygon
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
• Comments on a lower bound for convex hull determination
• How to reduce the average complexity of convex hull finding algorithms
• On the complexity of finding the convex hull of a set of points

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

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