Convex Hulls for Random Lines

DOI10.1006/JAGM.1993.1020MaRDI QIDQ4696647zbMATH OpenOpenAlexFDO

Authors Godfried Toussaint, Luc Devroye

Publication date 29 June 1993

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/6d3545a1fc8787da2b0144694140cf0711525f25

zbMATH Keywords

arrangementsdistanceslopeintersection points

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A linear algorithm for computing convex hulls for random lines
• Convex hull for intersections of random lines
• The mean number of extreme lines in a convex hull of lines
• Capturing crossings: convex hulls of segment and plane intersections
• On the convex hull of random points in a polytope

Cited in

(8)

• Capturing crossings: convex hulls of segment and plane intersections
• The mean number of extreme lines in a convex hull of lines
• A linear algorithm for computing convex hulls for random lines
• Convex hull for intersections of random lines
• Weak convergence of the intersection point process of Poisson hyperplanes
• A note on the expected time required to construct the outer layer
• Discrete and Computational Geometry
• Convex hull of points lying on lines in \(O(n\log n)\) time after preprocessing

This page was built for publication: Convex Hulls for Random Lines

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