Lower bounds for maximal and convex layers problems

DOI10.1007/BF01553901zbMath0684.68053OpenAlexW2024116303MaRDI QIDQ1825651

Sanjiv Kapoor, Prakash V. Ramanan

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01553901

zbMATH Keywords

upper boundlower boundtime complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10)

Related Items (4)

Records, the maximal layer, and uniform distributions in monotone sets ⋮ Distribution-sensitive algorithms ⋮ Optimal, output-sensitive algorithms for constructing planar hulls in parallel ⋮ Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems

Cites Work

• Unnamed Item
• Obtaining lower bounds using artificial components
• On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
• An efficient algorithm for determining the convex hull of a finite planar set
• On the convex layers of a planar set
• The Ultimate Planar Convex Hull Algorithm?
• A Lower Bound to Finding Convex Hulls
• Lower bounds for algebraic decision trees
• On Finding the Maxima of a Set of Vectors
• Convex hulls of finite sets of points in two and three dimensions
• An optimal real-time algorithm for planar convex hulls

This page was built for publication: Lower bounds for maximal and convex layers problems