inria-00072355, version 1

Complexity of the Delaunay triangulation of points on polyhedral surfaces

Dominique Attali ¹, Jean-Daniel Boissonnat ()

N° RR-4232 (2001)

• 1 :  PRISME (INRIA Sophia Antipolis)
• 
  INRIA France

Références bibliographiques

• Type de publication : Rapports
• Domaine : Informatique/Autre
• Titre : Complexity of the Delaunay triangulation of points on polyhedral surfaces
• 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$.
• Langue du document : Anglais
• Date de publication : 07/2001
• Mots-clés : COMPUTATIONAL GEOMETRY / DELAUNAY TRIANGULATION / POLYHEDRAL SURFACES / COMPLEXITY / SURFACE RECONSTRUCTION
• Date de rédaction : 07/2001
• Référence interne : RR-4232

Liste des fichiers attachés à ce document :

• inria-00072355, version 1
• http://hal.inria.fr/inria-00072355
• oai:hal.inria.fr:inria-00072355
• Contributeur : Rapport De Recherche Inria <>
• Soumis le : Mardi 23 Mai 2006, 20:30:48
• Dernière modification le : Mercredi 31 Mai 2006, 14:24:26