Skip to Main content Skip to Navigation
Conference papers

Convex hull for intersections of random lines

Abstract : 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.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184036
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 3:52:11 PM
Last modification on : Friday, December 18, 2020 - 6:46:05 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:29 AM

File

dmAD0105.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184036, version 1

Collections

Citation

Daniel Berend, Vladimir Braverman. Convex hull for intersections of random lines. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.39-48. ⟨hal-01184036⟩

Share

Metrics

Record views

208

Files downloads

1170