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

The restricted Delaunay triangulation of a closed surface $\mathrm{\Sigma }$ and a finite point set $V\subset \mathrm{\Sigma }$ is a subcomplex of the Delaunay tetrahedralization of $V$ whose triangles approximate $\mathrm{\Sigma }$. It is well known that if $V$ is a sufficiently dense sample of a smooth $\mathrm{\Sigma }$, then the union of the restricted Delaunay triangles is homeomorphic to $\mathrm{\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\mathrm{\Sigma }$ (the plane tangent to $\mathrm{\Sigma }$ at $v$) is star-shaped.