Splitting a Delaunay Triangulation in Linear Time

Bernard Chazelle (1) , Olivier Devillers (2) , Ferran Hurtado (3) , Mercè Mora (3) , Vera Sacristán (4) , Monique Teillaud (2)

1 Computer Science Department [Princeton]
2 PRISME - Geometry, Algorithms and Robotics
3 Departament de Matemàtica Aplicada II
4 UPC - Universitat Politècnica de Catalunya = Université polytechnique de Catalogne [Barcelona]

Computing the Delaunay triangulation of n points is well known to have an Ω(n log n) lower bound. Researchers have attempted to break that bound in special cases where additional information is known.

Domaines: Géométrie algorithmique [cs.CG]

Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Mercè Mora, Vera Sacristán, et al.. Splitting a Delaunay Triangulation in Linear Time. Proceedings of the 8th European Symposium on Algorithms, 2001, Aarhus, Denmark. pp.312-320, ⟨10.1007/3-540-44676-1_26⟩. ⟨hal-01179401⟩