2026-07-20T10:41:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25896 2026-06-23T13:00:24Z ddc:004 open_access

Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells Shewchuk, Jonathan Richard Restricted Delaunay triangulation restricted Voronoi diagram surface sampling surface mesh generation surface reconstruction ε-sample homeomorphism The restricted Delaunay triangulation of a closed surface Σ and a finite point set V ⊂ Σ 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 ε ≤ 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 ∈ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonathan Richard Shewchuk 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.90 urn:nbn:de:0030-drops-258961 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.90 eng https://creativecommons.org/licenses/by/4.0/legalcode