Skip to Main content Skip to Navigation

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction

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.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:09:15 AM
Last modification on : Thursday, January 20, 2022 - 4:14:52 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:11:04 PM


  • HAL Id : inria-00072510, version 1



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⟩



Les métriques sont temporairement indisponibles