A Linear Bound on the Complexity of the Delaunay triangulation of points on polyhedral surfaces

Abstract : Delaunay triangulations and Voronoi diagrams have found numerous applications in surface modeling, surface mesh generation, deformable surface modeling and surface reconstruction. Many algorithms in these applications begin by constructing the three-dimensional Delaunay triangulation of a finite set of points scattered over a surface. Their running-time therefore depends on the complexity of the Delaunay triangulation of such point sets. Although the Delaunay triangulation of points in ^3 can be quadratic in the worst-case, we show that, under some mild sampling condition, the complexity of the 3D Delaunay triangulation of points distributed on a fixed number of facets of ^3 (e.g. the facets of a polyhedron) is linear. Our bound is deterministic and the constants are explicitly given.
Document type :
Reports
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072135
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:53:03 PM
Last modification on : Tuesday, April 2, 2019 - 2:42:16 PM
Long-term archiving on : Sunday, April 4, 2010 - 10:54:51 PM

Identifiers

  • HAL Id : inria-00072135, version 1

Collections

Citation

Dominique Attali, Jean-Daniel Boissonnat. A Linear Bound on the Complexity of the Delaunay triangulation of points on polyhedral surfaces. [Research Report] RR-4453, INRIA. 2002. ⟨inria-00072135⟩

Share

Metrics

Record views

163

Files downloads

252