# Complexity of the Delaunay triangulation of points on polyhedral surfaces

Complexity of the Delaunay triangulation of points on polyhedral surfaces - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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} ceil }$. 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 $On^1.8$ for general polyhedral surfaces and $On\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$.

Keywords : COMPLEXITY SURFACE RECONSTRUCTION DELAUNAY TRIANGULATION POLYHEDRAL SURFACES COMPUTATIONAL GEOMETRY

Autor: Dominique Attali - Jean-Daniel Boissonnat

Fuente: https://hal.archives-ouvertes.fr/

DESCARGAR PDF