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. Our algorithm has the same asymptotic complexity as previous ones for this problem, but our algorithm is much simpler and it runs faster in practice than a direct computation of the Delaunay triangulation.
Type de document :
Article dans une revue
Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2011, 2 (1), pp.30-45. 〈http://jocg.org/v2n1p3〉. 〈10.20382/jocg.v2i1a3〉
Liste complète des métadonnées

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


https://hal.inria.fr/inria-00595823
Contributeur : Olivier Devillers <>
Soumis le : mercredi 25 mai 2011 - 16:10:13
Dernière modification le : jeudi 11 janvier 2018 - 16:16:55
Document(s) archivé(s) le : vendredi 26 août 2011 - 02:27:02

Fichiers

41-226-1-PB.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Olivier Devillers. Delaunay Triangulation of Imprecise Points, Preprocess and Actually Get a Fast Query Time. Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2011, 2 (1), pp.30-45. 〈http://jocg.org/v2n1p3〉. 〈10.20382/jocg.v2i1a3〉. 〈inria-00595823〉

Partager

Métriques

Consultations de la notice

220

Téléchargements de fichiers

205