Minimal set of constraints for 2D constrained Delaunay reconstruction

Olivier Devillers 1 Regina Estkowski 2 Pierre-Marie Gandoin 3 Ferran Hurtado 4 Pedro Ramos Vera Sacristán 4
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 Computer Science Department [SUNY]
3 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
4 UPC - Universitat Politècnica de Catalunya [Barcelona]
Abstract : Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T) using constrained Delaunay triangulation. We show that this minimal set is precisely the set of non locally Delaunay edges, and that its cardinality is less than or equal to n+i/2 (if i is the number of interior points in T), which is a tight bound.
Document type :
Journal articles
Complete list of metadatas
https://hal.inria.fr/hal-00787186
Contributor : Olivier Devillers <>
Submitted on : Monday, February 11, 2013 - 3:19:21 PM
Last modification on : Tuesday, August 13, 2019 - 11:22:21 AM

Links full text

openaccess

Identifiers

Collections

INRIA | LABEXIMU

Citation

Olivier Devillers, Regina Estkowski, Pierre-Marie Gandoin, Ferran Hurtado, Pedro Ramos, et al.. Minimal set of constraints for 2D constrained Delaunay reconstruction. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2003, 13 (5), pp.391-398. ⟨10.1142/S0218195903001244⟩. ⟨hal-00787186⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

280

Contact

Informations

CCSD