inria-00090664, version 1
Splitting a Delaunay Triangulation in Linear Time
Bernard Chazelle a, 1Olivier Devillers
b, 2Ferran Hurtado c, 3Merce Mora c, 3Vera Sacristan c, 3Monique Teillaud b, 2
Algorithmica 34, 1 (2002) 39--46
Résumé : 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.
- a – Princeton University
- b – INRIA
- c – Universitat Politécnica de Catalunya
- 1 : Computer Science Department
- Princeton University
- 2 : GEOMETRICA (INRIA Sophia Antipolis)
- INRIA
- 3 : Departament de Matemàtica Aplicada II
- Universitat Politécnica de Catalunya
- Domaine : Informatique/Géométrie algorithmique
- Commentaire : http://www.springerlink.com/content/klucy2713wy40m41/
- inria-00090664, version 1
- http://hal.inria.fr/inria-00090664
- oai:hal.inria.fr:inria-00090664
- Contributeur : Olivier Devillers
- Soumis le : Vendredi 1 Septembre 2006, 16:02:18
- Dernière modification le : Vendredi 1 Septembre 2006, 16:06:33
Documents associés
Exporter