On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination

DOI10.1016/0020-0190(80)90064-2zbMath0435.68033OpenAlexW2079059509MaRDI QIDQ1140425

Peter van Emde Boas

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)90064-2

zbMATH Keywords

convex hulllinear decision treemaximal vectorgeometrical complexitylinear search treelowerbound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

A variant of Ben-Or's lower bound for algebraic decision trees, Connecting colored point sets, An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons, Comments on a lower bound for convex hull determination, Linear decision trees are too weak for convex hull problem, On the complexity of finding the convex hull of a set of points, Maintenance of configurations in the plane, Comparisons between linear functions can help, Lower bounds for maximal and convex layers problems, On constant factors in comparison-based geometric algorithms and data structures, Some dynamic computational geometry problems

Cites Work

• Unnamed Item
• Unnamed Item
• A linear algorithm for finding the convex hull of a simple polygon
• On the complexity of finding the convex hull of a set of points
• On the complexity of computations under varying sets of primitives
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• A Lower Bound to Finding Convex Hulls
• On Finding the Maxima of a Set of Vectors
• Convex hulls of finite sets of points in two and three dimensions
• A New Convex Hull Algorithm for Planar Sets
• On the complexity of computing the measure of ∪[a _i ,b _i ]