8481 articles  [english version]

inria-00072355, version 1

## Complexity of the Delaunay triangulation of points on polyhedral surfaces

Dominique Attali 1, Jean-Daniel Boissonnat ()

N° RR-4232 (2001)

Résumé : 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$.

• 1 :  PRISME (INRIA Sophia Antipolis)
• INRIA
• Domaine : Informatique/Autre
• Mots-clés : COMPUTATIONAL GEOMETRY / DELAUNAY TRIANGULATION / POLYHEDRAL SURFACES / COMPLEXITY / SURFACE RECONSTRUCTION
• Référence interne : RR-4232

• inria-00072355, version 1
• oai:hal.inria.fr:inria-00072355
• Contributeur :
• Soumis le : Mardi 23 Mai 2006, 20:30:48
• Dernière modification le : Mercredi 31 Mai 2006, 14:24:26