Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells
This improves computational geometry methods for surface meshing, offering more efficient sampling for applications like computer graphics and simulations, though it is incremental over existing bounds.
The paper tackles the problem of approximating smooth surfaces with restricted Delaunay triangulations by improving sampling bounds, showing that an ε-sample with ε ≤ 0.3245 suffices for homeomorphism, reducing required sample points by factors of 3.25 and 21 compared to prior work.
The restricted Delaunay triangulation of a closed surface $Σ$ and a finite point set $V \subset Σ$ is a subcomplex of the Delaunay tetrahedralization of $V$ whose triangles approximate $Σ$. It is well known that if $V$ is a sufficiently dense sample of a smooth $Σ$, then the union of the restricted Delaunay triangles is homeomorphic to $Σ$. We show that an $ε$-sample with $ε\leq 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Σ$ (the plane tangent to $Σ$ at $v$) is star-shaped.