A linear algorithm for computing convex hulls for random lines

DOI10.1145/1597036.1597046MaRDI QIDQ2930268zbMATH OpenOpenAlexFDO

Authors 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 complexitycomputational geometryconvex hullrandom linesrandomized algorithms

Mathematics Subject Classification ID

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

Recommendations

• Convex Hulls for Random Lines
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
• Convex hull for intersections of random lines
• scientific article; zbMATH DE number 17632
• Small-dimensional linear programming and convex hulls made easy

Cited in

(14)

• Computing the convex hull in a hammock
• The mean number of extreme lines in a convex hull of lines
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing
• The generalized yolk point
• A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square
• scientific article; zbMATH DE number 17632 (Why is no real title available?)
• Convex Hulls for Random Lines
• Convex hull of imprecise points in o(n n) time after preprocessing
• Computing hereditary convex structures
• Convex hull for intersections of random lines
• Discrete and Computational Geometry
• An algorithm to find the lineality space of the positive hull of a set of vectors
• Randomized quickhull
• Capturing crossings: convex hulls of segment and plane intersections

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

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