Convex hull for intersections of random lines - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

Convex hull for intersections of random lines

Résumé

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.
Fichier principal
Vignette du fichier
dmAD0105.pdf (124.58 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184036 , version 1 (12-08-2015)

Identifiants

Citer

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⟩

Collections

INSMI TDS-MACS
126 Consultations
788 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More