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 triangulati- on. We show that this minimal set consists of the non locally Delaunay edges of $T$, 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.
https://hal.inria.fr/inria-00072510
Contributor : Rapport de Recherche Inria
<>
Submitted on : Wednesday, May 24, 2006 - 10:09:15 AM
Last modification on : Tuesday, February 26, 2019 - 11:19:50 AM
Long-term archiving on : Sunday, April 4, 2010 - 11:11:04 PM
Olivier Devillers, Regina Estkowski, Pierre-Marie Gandoin, Ferran Hurtado, Pedro Ramos, et al.. Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction. RR-4119, INRIA. 2001. ⟨inria-00072510⟩
