Daniel Berend
Senior Academic
Convex hull for intersections of random lines
The problem of finding the convex hull of the intersection points of random lines was studied in Devroye and Toussaint, 1993 and Langerman, Golin and Steiger, 2002, and algorithms with expected linear time were found. We improve the previous results of the model in Devroye and Toussaint, 1993 by giving a universal algorithm for a wider range of distributions.
| Publication language | English |
| Journal | Discrete Mathematics and Theoretical Computer Science |
| Publication status | Published - 2005 |
Keywords
Data Structures and Algorithms
Computer Science
Mathematics
Computational Geometry
Combinatorics
Human-Computer Interaction
Discrete Mathematics
