Perturbations and Vertex Removal in a 3D Delaunay Triangulation

Olivier Devillers 1 Monique Teillaud 2
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
2 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Though Delaunay triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional Delaunay triangulation is still a problem in practice. We propose a simple method that allows to remove any vertex even when the points are in very degenerate configurations. The solution is available in \cgal\footnote{\texttt- {http://www.cgal.org} (releases 2.3 and 2.4)}.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00071961
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:22:11 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Long-term archiving on : Sunday, April 4, 2010 - 10:46:27 PM

Identifiers

  • HAL Id : inria-00071961, version 1

Citation

Olivier Devillers, Monique Teillaud. Perturbations and Vertex Removal in a 3D Delaunay Triangulation. RR-4624, INRIA. 2002. ⟨inria-00071961⟩

Share

Metrics

Record views

262

Files downloads

234