A linear algorithm for computing convex hulls for random lines

DOI10.1145/1597036.1597046zbMATH Open1298.68274OpenAlexW1984470259MaRDI QIDQ2930268

Daniel Berend, Vladimir Braverman

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1597036.1597046

zbMATH Keywords

computational complexityconvex hullcomputational geometryrandomized algorithmsrandom lines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)

Related Items (1)

An algorithm to find the lineality space of the positive hull of a set of vectors

This page was built for publication: A linear algorithm for computing convex hulls for random lines