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

Complexity of the Delaunay triangulation of points on polyhedral surfaces

Dominique Attali 1 Jean-Daniel Boissonnat
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : It is well known that the complexity of the Delaunay triangulation of $n$ points in $R ^d$, i.e. the number of its simplices, can be $\Omega (n^\lceil \frac{d{2}\rceil })$. In particular, in $R ^3$, the number of tetrahedra can be quadratic. Differently, if the points are uniformly distributed in a cube or a ball, the expected complexity of the Delaunay triangulation is only linear. The case of points distributed on a surface is of great practical importance in reverse engineering since most surface reconstruction algorithms first construct the Delaunay triangulation of a set of points measured on a surface. In this paper, we bound the complexity of the Delaunay triangulation of points distributed on the boundary of a given polyhedron. Under a mild uniform sampling condition, we provide deterministic asymptotic bounds on the complexity of the 3D Delaunay triangula- tion of the points when the sampling density increases. More precisely, we show that the complexity is $O(n^1.8)$ for general polyhedral surfaces and $O(n\sqrtn)$ for convex polyhedral surfaces. Our proof uses a geometric result of independent interest that states that the medial axis of a surface is well approximated by a subset of the Voronoi vertices of the sample points. The proof extends easily to higher dimensions, leading to the first non trivial bounds for the problem when $d>3$.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 8:30:48 PM
Last modification on : Friday, February 4, 2022 - 3:16:18 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:05:14 PM


  • HAL Id : inria-00072355, version 1



Dominique Attali, Jean-Daniel Boissonnat. Complexity of the Delaunay triangulation of points on polyhedral surfaces. RR-4232, INRIA. 2001. ⟨inria-00072355⟩



Record views


Files downloads