Linear decision trees are too weak for convex hull problem

DOI10.1016/0020-0190(81)90112-5zbMATH Open0466.68058OpenAlexW2060561824MaRDI QIDQ1155366FDOQ1155366

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

Cites Work

• An efficient algorithm for determining the convex hull of a finite planar set
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of computations under varying sets of primitives
• A Lower Bound to Finding Convex Hulls
• 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 finding the convex hull of a set of points

Cited In (1)

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

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

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