HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

# Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction

1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Mots-clés :
Document type :
Reports
Domain :
Complete list of metadata

https://hal.inria.fr/inria-00072510
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 : Friday, February 4, 2022 - 3:16:07 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:11:04 PM

### Identifiers

• HAL Id : inria-00072510, version 1

### Citation

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⟩

Record views

Files downloads