Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells

Abstract

The restricted Delaunay triangulation of a closed surface $\Sigma$ and a finite point set $V\subset \Sigma$ is a subcomplex of the Delaunay tetrahedralization of $V$ whose triangles approximate $\Sigma$. It is well known that if $V$ is a sufficiently dense sample of a smooth $\Sigma$, then the union of the restricted Delaunay triangles is homeomorphic to $\Sigma$. We show that an $\epsilon$-sample with $\epsilon \le 0.3245$ suffices. By comparison, Dey proves it for a $0.18$-sample; our improved sampling bound reduces the number of sample points required by a factor of $3.25$. More importantly, we improve a related sampling bound of Cheng et al. for Delaunay surface meshing, reducing the number of sample points required by a factor of $21$. The first step of our homeomorphism proof is particularly interesting: we show that for a $0.44$-sample, the restricted Voronoi cell of each site $v\in V$ is homeomorphic to a disk, and the orthogonal projection of the cell onto $T_v\Sigma$ (the plane tangent to $\Sigma$ at $v$) is star-shaped.

arXiv comment24 pages, 8 figures. Extended version (with complete proofs) of a paper that will appear in the 42nd International Symposium on Computational Geometry