 |
 |
 |
Conference papers
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
Bernard Chazelle 1
Author Employer institution : Princeton University
Olivier Devillers 2
Author Employer institution : Institut National de Recherche en Informatique et en Automatique IdHAL : olivierdevillers ORCID : https://orcid.org/0000-0003-4275-5068
Ferran Hurtado 3
Author
Mercè Mora 3
Author
Vera Sacristán 4
Author
Monique Teillaud 2
Author IdHAL : monique-teillaud ORCID : https://orcid.org/0000-0003-2568-7024
1
Computer Science Department [Princeton] (Princeton University
35 Olden Street, Princeton, NJ 08540-5233 - United States)
- Princeton University (Princeton, NJ 08544 USA - United States)
2
PRISME - Geometry, Algorithms and Robotics (France)
- CRISAM - Inria Sophia Antipolis - Méditerranée (2004 route des Lucioles BP 93 06902 Sophia Antipolis - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
3
Departament de Matemàtica Aplicada II (Universitat Politècnica de Catalunya (UPC) Edifici Omega, Campus Nord Jordi Girona, 1-3 E-08034 Barcelona Spain - Spain)
- UPC - Universitat Politècnica de Catalunya [Barcelona] (C./Jordi Girona, 1-3, 08034 Barcelona - Spain)
4
UPC - Universitat Politècnica de Catalunya [Barcelona] (C./Jordi Girona, 1-3, 08034 Barcelona - Spain)
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 : Monday, November 16, 2020 - 3:56:03 PM
Contributor : Olivier Devillers <>
Submitted on : Wednesday, July 22, 2015 - 2:17:02 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Identifiers
- HAL Id : hal-01179401, version 1
- DOI : 10.1007/3-540-44676-1_26
Collections
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⟩
Metrics
Record views