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
CRISAM - Inria Sophia Antipolis - Méditerranée
3 Departament de Matemàtica Aplicada II
4 UPC - Universitat Politècnica de Catalunya [Barcelona]
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas
https://hal.inria.fr/hal-01179401
Contributor : Olivier Devillers <>
Submitted on : Wednesday, July 22, 2015 - 2:17:02 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM

Identifiers

Collections

INRIA

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

229

Contact

CCSD