Delaunay triangulation of imprecise points, preprocess and actually get a fast query time

Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We propose a new algorithm to preprocess a set of n disjoint unit disks in O(n log n) expected time, allowing to compute the Delaunay triangulation of a set of n points, one from each disk, in O(n) expected time. This work reaches the same asymptotical theoretical complexities as previous results on this problem, but our algorithm is much simpler and efficient in practice.
Type de document :
Communication dans un congrès
XIV Spanish Meeting on Computational Geometry,, 2011, Alcala de Henares, Spain. 2011
Liste complète des métadonnées

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


https://hal.inria.fr/hal-00850583
Contributeur : Olivier Devillers <>
Soumis le : mercredi 7 août 2013 - 13:24:52
Dernière modification le : jeudi 11 janvier 2018 - 16:39:00
Document(s) archivé(s) le : mercredi 5 avril 2017 - 19:42:14

Fichiers

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00850583, version 1

Collections

Citation

Olivier Devillers. Delaunay triangulation of imprecise points, preprocess and actually get a fast query time. XIV Spanish Meeting on Computational Geometry,, 2011, Alcala de Henares, Spain. 2011. 〈hal-00850583〉

Partager

Métriques

Consultations de la notice

268

Téléchargements de fichiers

137