Splitting a Delaunay Triangulation in Linear Time

Abstract : Computing the Delaunay triangulation of n points requires usually a minimum of Omega(n log n) operations, but in some special cases where some additional knowledge is provided, faster algorithms can be designed. Given two sets of points, we prove that, if the Delaunay triangulation of all the points is known, the Delaunay triangulation of each set can be computed in randomized expected linear time.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2002, 34 (1), pp.39--46. 〈10.1007/s00453-002-0939-8〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00090664
Contributeur : Olivier Devillers <>
Soumis le : vendredi 1 septembre 2006 - 16:02:18
Dernière modification le : samedi 27 janvier 2018 - 01:31:22
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:44:03

Identifiants

Collections

Citation

Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Mercè Mora, Vera Sacristan, et al.. Splitting a Delaunay Triangulation in Linear Time. Algorithmica, Springer Verlag, 2002, 34 (1), pp.39--46. 〈10.1007/s00453-002-0939-8〉. 〈inria-00090664〉

Partager

Métriques

Consultations de la notice

324

Téléchargements de fichiers

285