Applications of random sampling to on-line algorithms in computational geometry

Abstract : This paper presents a general framework for the design and randomized analysis of geometric algorithms. These algorithms are on-line and the framework provides general bounds for their expected space and time complexities when averaging over all permutations of the input data. The method is general and can be applied to various geometric problems. The power of the technique is illustrated by new efficient on-line algorithms for constructing convex hulls and Voronoi diagrams in any dimension, Voronoi diagrams of line segments in the plane, arrangements of curves in the plane, and others.
Type de document :
Article dans une revue
Discrete and Computational Geometry, Springer Verlag, 1992, 8 (1), pp.51--71. 〈10.1007/BF02293035〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00090675
Contributeur : Olivier Devillers <>
Soumis le : vendredi 1 septembre 2006 - 16:10:06
Dernière modification le : vendredi 12 janvier 2018 - 01:50:29
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:44:09

Fichier

Identifiants

Citation

Jean-Daniel Boissonnat, Olivier Devillers, René Schott, Monique Teillaud, Mariette Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discrete and Computational Geometry, Springer Verlag, 1992, 8 (1), pp.51--71. 〈10.1007/BF02293035〉. 〈inria-00090675〉

Partager

Métriques

Consultations de la notice

324

Téléchargements de fichiers

93