Linear decision trees are too weak for convex hull problem

DOI10.1016/0020-0190(81)90112-5zbMath0466.68058OpenAlexW2060561824MaRDI QIDQ1155366

Jerzy W. Jaromczyk

Publication date: 1981

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

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90112-5

zbMATH Keywords

computational geometry

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

A variant of Ben-Or's lower bound for algebraic decision trees

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• On the complexity of computations under varying sets of primitives
• An efficient algorithm for determining the convex hull of a finite planar set
• A Lower Bound to Finding Convex Hulls

This page was built for publication: Linear decision trees are too weak for convex hull problem