Comments on a lower bound for convex hull determination

DOI10.1016/0020-0190(80)90125-8zbMath0455.68027OpenAlexW2017193814MaRDI QIDQ1150269

David Avis

Publication date: 1980

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(80)90125-8

zbMATH Keywords

geometric complexitylinear search tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (4)

A variant of Ben-Or's lower bound for algebraic decision trees ⋮ Linear decision trees are too weak for convex hull problem ⋮ On the complexity of finding the convex hull of a set of points ⋮ Randomized quickhull

Cites Work

• On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
• On the complexity of finding the convex hull of a set of points
• A Lower Bound to Finding Convex Hulls

This page was built for publication: Comments on a lower bound for convex hull determination