Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces |
| |
Authors: | Dominique Attali and Jean-Daniel Boissonnat |
| |
Institution: | (1) LIS, ENSIEG, Domaine Universitaire, BP 46, 38402 Saint Martin d Hères Cedex, France;(2) INRIA, Unité de Recherche Sophia Antipolis, 2004 Route des Lucioles, BP 93, 06904 Sophia-Antipolis, France |
| |
Abstract: | It is well known that the complexity of the Delaunay
triangulation of $n$ points in $\RR ^d$, i.e., the number of its
simplices, can be $\Omega (n^{\lceil {d}/{2}\rceil })$. In
particular, in $\RR ^3$, the number of tetrahedra can be quadratic.
Put another way, 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 three-dimensional Delaunay triangulation 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\sqrt{n})$ 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|