Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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


Publisher files allowed on an open archive




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



Record views


Files downloads