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 : jeudi 11 janvier 2018 - 16:36:53
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

298

Téléchargements de fichiers

258