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.
Type de document :
Communication dans un congrès
Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.39-48, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184036
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 15:52:11
Dernière modification le : samedi 17 février 2018 - 17:46:02
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:40:29

Fichier

dmAD0105.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184036, version 1

Collections

Citation

Daniel Berend, Vladimir Braverman. Convex hull for intersections of random lines. Conrado Martínez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.39-48, 2005, DMTCS Proceedings. 〈hal-01184036〉

Partager

Métriques

Consultations de la notice

122

Téléchargements de fichiers

209