8494 articles  [version française]

inria-00072510, version 1

Minimal Set of Constraints for 2D Constrained Delaunay Reconstruction

Olivier Devillers () 1, Regina Estkowski, Pierre-Marie Gandoin, Ferran Hurtado, Pedro Ramos, Vera Sacristán

N° RR-4119 (2001)

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.

  • 1:  PRISME (INRIA Sophia Antipolis)
  • INRIA
  • Domain : Computer Science/Other
  • Keywords : TRIANGULATION / DELAUNAY / $2$D / RECONSTRUCTION / MINIMAL CONSTRAINTS SET
  • Internal note : RR-4119
 
  • inria-00072510, version 1
  • http://hal.inria.fr/inria-00072510
  • oai:hal.inria.fr:inria-00072510
  • From: Rapport De Recherche Inria <>
  • Submitted on: Wednesday, 24 May 2006 10:09:15
  • Updated on: Wednesday, 31 May 2006 14:24:26