Sampling-density-only accuracy bounds for discrete surface approximation: extension to general triangulations, off-surface samples, and practical surface Delaunay constructions

Dai et al. (2007) proved that the piecewise-linear mesh induced by the (intrinsic) surface Delaunay triangulation — every triangle has a geodesically empty circumcircle on the surface — of an $\varepsilon$-sample of a closed $C^2$ surface approximates the surface with Hausdorff error at most $4k\varepsilon^2$, normal error at most $9k\varepsilon$, and metric distortion of order $k\varepsilon$ (explicitly, $1-4k^2\varepsilon^2\le dl_M/dl\le(1+4k^2\varepsilon^2)/(1-9k\varepsilon)$), where $k$ bounds the principal curvatures and $\varepsilon$ the sampling radius — bounds that depend on sampling density alone, with no mesh-regularity assumption. The paper left open how this ideal-case theory extends to the settings met in practice: (i) general (non-Delaunay) triangulations, with precise constants and the full range of admissible triangle-shape conditions; (ii) samples displaced off the surface (noise); (iii) consistency of practically computable constructions (restricted ambient Delaunay triangulations; planar Delaunay lifted through a numerically computed conformal parameterization) with the ideal surface Delaunay triangulation; and (iv) a convergence proof for its own conformal-parameterization pipeline. The problem asks for quantitative error bounds — or impossibility results — with explicit constants completing this extension program.

Background

Approximating a smooth surface by a polyhedral one. Let $S\subset\mathbb{R}^3$ be a closed (compact, without boundary) surface of class $C^2$, and let $M$ be a piecewise-linear (PL) surface with vertices on $S$, intended as a discrete approximation of $S$. Three standard measures of geometric accuracy are: the Hausdorff distance $d_H(M,S)$, the smallest $r$ such that every point of each of the two sets lies within Euclidean distance $r$ of the other set; the normal error $d_n(M,S)$, the maximum angle between the unit normal of $M$ at a point and the unit normal of $S$ at a closest point of $S$; and the metric distortion: at each point and in each tangent direction, the ratio $dl_M/dl$ between the length element of $M$ under its intrinsic (polyhedral) metric and the length element of $S$. Metric accuracy matters because discrete differential operators — for example discrete Laplace–Beltrami operators, the triangulated-surface analogues of the intrinsic surface Laplacian — and geodesic computations on $M$ inherit their accuracy from it.

Sampling conditions and geometric scales. A finite set $X\subset S$ is an $\varepsilon$-sample if every point of $S$ lies within geodesic distance $\varepsilon$ of some point of $X$. The relevant scales of $S$ are: a bound $k$ on the absolute values of the principal curvatures; the injectivity radius $\tau$ (the largest radius up to which geodesics minimize and geodesic balls are disks); and the local feature size $f$, the distance from a point of $S$ to the medial axis of $S$ (the set of points with more than one nearest point on $S$).

Prior results. Voronoi-filtering surface reconstruction (Amenta and Bern, 1999) achieved Hausdorff guarantees while assuming, rather than proving, a bound on the normal error of the sample. Morvan and Thibert (2002, 2004) bounded the normal and area errors of a triangulated mesh in terms of its Hausdorff error plus angle-type regularity conditions on the mesh. Hildebrandt, Polthier and Wardetzky (2006) proved that for sufficiently regular meshes ($\eta$-uniform triangulations, in which every angle is bounded below by a fixed constant $\eta>0$) the convergence of the polyhedral metric, of normals, and of related geometric quantities are equivalent — with mesh regularity as a hypothesis, not a conclusion. Leibon and Letscher (2000) established existence of Delaunay triangulations on Riemannian manifolds; Boissonnat and Oudot (2005) developed provably good surface meshing via the restricted Delaunay triangulation, the dual of the ambient Voronoi diagram of the sample restricted to the surface; Dyer, Zhang and Möller (2008) gave intrinsic sampling criteria (involving the strong convexity radius — the largest radius for which geodesic balls on $S$ are geodesically convex — and the injectivity radius) under which intrinsic Voronoi and Delaunay structures on a surface are topologically faithful.

The source result. A triangulation of a sample on a surface is a surface Delaunay (or intrinsic/geodesic Delaunay) triangulation if every triangle admits a geodesically empty circumcircle on $S$: a geodesic disk on $S$ whose boundary circle passes through the three vertices and whose interior contains no other sample point. Dai et al. (2007) proved that if $X$ is an $\varepsilon$-sample of $S$ with $\varepsilon\le\min\{2\tau/5,\,2\pi/(5k),\,f/4,\,1/(8k)\}$ and $M$ is the mesh induced by the surface Delaunay triangulation of $X$, then

$d_H(M,S)\le 4k\varepsilon^2,$

$d_n(M,S)\le 9k\varepsilon,$

$1-4k^2\varepsilon^2\le dl_M/dl\le(1+4k^2\varepsilon^2)/(1-9k\varepsilon).$

The proof rests on a shape-independent height lemma (for a geodesic triangle on $S$ of maximal geodesic edge length $d\le 1/k$, every point of the triangle is at Euclidean distance at most $k d^2/4$ from the plane through its three vertices) and on the bound of $2\varepsilon$ on the geodesic circumradius of surface Delaunay triangles. Crucially, these are sampling-density-only bounds: the Delaunay property itself supplies the shape control that excludes thin, obtuse triangles, so no separate mesh-regularity assumption is needed. The paper also described a practical pipeline to realize the construction: compute a conformal parameterization of $S$ (an angle-preserving bijection) onto a canonical domain — sphere, flat torus, or hyperbolic disk, according to the genus, that is the number of handles, of $S$ — in practice from a coarse initial mesh; place area-weighted samples in the parameter domain; map the samples barycentrically back onto $S$ through the initial mesh (a sample inside a triangle of the domain mesh is sent to the point of the corresponding initial-mesh triangle with the same barycentric coordinates); compute the planar Delaunay triangulation in the domain; and lift it to the surface. The distance between what this pipeline computes and what the theorems assume is the subject of the open questions below.

Problem Statement

Let $S\subset\mathbb{R}^3$ be a closed (compact, without boundary) surface of class $C^2$ whose principal curvatures are bounded in absolute value by $k$, with injectivity radius $\tau$ (the largest radius up to which geodesics minimize and geodesic balls are disks) and local feature size $f$ (the distance from a point of $S$ to the medial axis of $S$, the set of points with more than one nearest point on $S$). Let $X\subset S$ be an $\varepsilon$-sample of $S$ (every point of $S$ within geodesic distance $\varepsilon$ of some point of $X$). For a mesh $M$ with vertices on $S$: $d_H(M,S)$ is the Hausdorff distance (the smallest $r$ such that every point of each of $M$ and $S$ lies within Euclidean distance $r$ of the other); $d_n(M,S)$ is the maximum angle between the unit normal of $M$ and the unit normal of $S$ at a closest point of $S$; and $dl_M/dl$ is the pointwise ratio of the length element of $M$ under its intrinsic polyhedral metric to the length element of $S$ (metric convergence means this ratio tends to 1 uniformly). Dai et al. (2007) proved that if $\varepsilon\le\min\{2\tau/5,\,2\pi/(5k),\,f/4,\,1/(8k)\}$ and $M$ is the mesh induced by the surface Delaunay triangulation of $X$ (every triangle's three vertices lie on a geodesic circle of $S$ whose geodesic disk interior contains no other sample point), then $d_H(M,S)\le 4k\varepsilon^2$, $d_n(M,S)\le 9k\varepsilon$, and $1-4k^2\varepsilon^2\le dl_M/dl\le(1+4k^2\varepsilon^2)/(1-9k\varepsilon)$.

The problem is to extend this sampling-density-only accuracy theory from the ideal setting (exact on-surface samples; ideal surface Delaunay triangulation) to the general and practical setting, as left open by that work. The extension program has the following parts, each requiring explicit constants:

(1) General triangulations. Determine the admissible triangle-shape conditions under which an arbitrary triangulation of $X$ — not necessarily Delaunay — satisfies bounds of the same order: give a shape condition that is sufficient, with explicit constants in all three bounds; and establish necessity, by constructing surfaces, $\varepsilon$-samples, and triangulations violating the condition for which no sampling-density-only bound of that order can hold (in particular for the normal and metric errors).

(2) Off-surface and noisy samples. Suppose the input is a finite set $Y\subset\mathbb{R}^3$ with $\max_{y\in Y}\mathrm{dist}(y,S)\le\delta$, whose nearest-point projection to $S$ is an $\varepsilon$-sample (worst-case displacement $\delta$; high-probability versions under random-noise models are also admissible). Define the appropriate mesh construction on $Y$ and prove explicit bounds on $d_H$, $d_n$, and $dl_M/dl$ quantifying the degradation as a function of $\delta/\varepsilon$ and identifying the regime in which the quadratic Hausdorff rate and the linear normal rate survive; or prove impossibility — that beyond an explicit threshold on $\delta$ no mesh constructible from $Y$ achieves these rates.

(3) Practical consistency. Prove or disprove, under explicit sampling and accuracy conditions: (a) the planar Delaunay triangulation computed on a numerically obtained discrete conformal parameterization of $S$ — an angle-preserving map computed from a coarse initial mesh — induces, after lifting to $S$, exactly or approximately the surface Delaunay triangulation, with a quantified notion of approximation; and (b) the restricted Delaunay triangulation (dual of the ambient Voronoi diagram of the sample restricted to $S$) coincides with the intrinsic surface Delaunay triangulation — for which conditions are known for $\delta$-generic samples (Boissonnat, Dyer and Ghosh; $\delta$-genericity is a mild general-position condition on the sample, satisfied after an arbitrarily small perturbation); the open parts are the conformal route (a) and the removal of genericity assumptions in (b).

(4) Pipeline convergence. Give a complete convergence proof, with explicit rates and constants, for the source's actual pipeline: (i) a coarse initial mesh and a numerically computed discrete conformal parameterization; (ii) area-weighted random samples in the parameter domain; (iii) barycentric mapping of the samples onto $S$ through the initial mesh — a sample inside a triangle of the domain mesh is sent to the point of the corresponding initial-mesh triangle with the same barycentric coordinates — so the samples lie on the initial PL approximation, not exactly on $S$; (iv) planar Delaunay triangulation in the domain; (v) lifting to the surface. The proof must account for the parameterization error, the sampling distortion, and the off-surface displacement of the lifted samples, and conclude bounds on $d_H$, $d_n$, and $dl_M/dl$. (For the variant with an exact conformal parameterization and Delaunay refinement — a meshing strategy that inserts new samples at triangle circumcenters until all triangles meet a size criterion — this was resolved by Li et al. (2014); the plain-sampling, numerical-parameterization variant remains open.)

The four parts share one scientific objective: replacing the idealized hypotheses of the 2007 accuracy theory by the conditions actually met in practice, so that the geometric accuracy of a discrete surface approximation can be certified from the sampling density, the noise level, and identified shape conditions alone.

References

1. Junfei Dai, Wei Luo, Miao Jin, Wei Zeng, Ying He, Shing-Tung Yau, Xianfeng Gu. Geometric accuracy analysis for discrete surface approximation. Computer Aided Geometric Design 24(6):323-338, 2007. DOI: 10.1016/j.cagd.2007.04.004. https://doi.org/10.1016/j.cagd.2007.04.004
2. Nina Amenta, Marshall Bern. Surface Reconstruction by Voronoi Filtering. Discrete and Computational Geometry 22(4):481-504, 1999. DOI: 10.1007/PL00009475. https://doi.org/10.1007/PL00009475
3. Greg Leibon, David Letscher. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In Proceedings of the Sixteenth Annual Symposium on Computational Geometry (SoCG 2000), pages 341-349, 2000. DOI: 10.1145/336154.336221. https://doi.org/10.1145/336154.336221
4. Jean-Marie Morvan, Boris Thibert. On the approximation of a smooth surface with a triangulated mesh. Computational Geometry: Theory and Applications 23(3):337-352, 2002. DOI: 10.1016/S0925-7721(02)00097-4. https://doi.org/10.1016/S0925-7721(02)00097-4
5. Jean-Marie Morvan, Boris Thibert. Approximation of the Normal Vector Field and the Area of a Smooth Surface. Discrete and Computational Geometry 32(3):383-400, 2004. DOI: 10.1007/s00454-004-1096-4. https://doi.org/10.1007/s00454-004-1096-4
6. Jean-Daniel Boissonnat, Steve Oudot. Provably good sampling and meshing of surfaces. Graphical Models 67(5):405-451, 2005. DOI: 10.1016/j.gmod.2005.01.004. https://doi.org/10.1016/j.gmod.2005.01.004
7. Klaus Hildebrandt, Konrad Polthier, Max Wardetzky. On the convergence of metric and geometric properties of polyhedral surfaces. Geometriae Dedicata 123(1):89-112, 2006. DOI: 10.1007/s10711-006-9109-5. https://doi.org/10.1007/s10711-006-9109-5
8. Tamal K. Dey, Samrat Goswami. Provable surface reconstruction from noisy samples. Computational Geometry: Theory and Applications 35(1-2):124-141, 2006. DOI: 10.1016/j.comgeo.2005.10.006. https://doi.org/10.1016/j.comgeo.2005.10.006
9. Ramsay Dyer, Hao Zhang, Torsten Möller. Surface sampling and the intrinsic Voronoi diagram. Computer Graphics Forum 27(5):1393-1402, 2008. DOI: 10.1111/j.1467-8659.2008.01279.x. https://doi.org/10.1111/j.1467-8659.2008.01279.x
10. Jean-Daniel Boissonnat, Arijit Ghosh. Triangulating Smooth Submanifolds with Light Scaffolding. Mathematics in Computer Science 4(4):431-461, 2010 (issue dated December 2010; published online 1 September 2011). DOI: 10.1007/s11786-011-0066-5. https://doi.org/10.1007/s11786-011-0066-5
11. Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Constructing Intrinsic Delaunay Triangulations of Submanifolds. Research Report RR-8273, INRIA, 2013. arXiv:1303.6493. https://arxiv.org/abs/1303.6493
12. Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. Delaunay triangulation of manifolds. Foundations of Computational Mathematics 18(2):399-431, 2018. DOI: 10.1007/s10208-017-9344-1. https://doi.org/10.1007/s10208-017-9344-1
13. Huibin Li, Wei Zeng, Jean-Marie Morvan, Liming Chen, Xianfeng David Gu. Surface Meshing with Curvature Convergence. IEEE Transactions on Visualization and Computer Graphics 20(6):919-934, 2014. DOI: 10.1109/TVCG.2013.253. https://doi.org/10.1109/TVCG.2013.253
14. Wen-Yong Gong, Yong-Jin Liu, Kai Tang, Tie-Ru Wu. 2-Manifold Surface Sampling and Quality Estimation of Reconstructed Meshes. In 2011 Eighth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), pages 15-22, 2011. DOI: 10.1109/ISVD.2011.11. https://doi.org/10.1109/ISVD.2011.11
15. Wenyong Gong, Yong-Jin Liu, Kai Tang, Tieru Wu. Approximate Delaunay mesh reconstruction and quality estimation from point samples. Journal of Computational and Applied Mathematics 274:23-34, 2015. DOI: 10.1016/j.cam.2014.07.001. https://doi.org/10.1016/j.cam.2014.07.001
16. Marc Khoury, Jonathan Richard Shewchuk. Approximation Bounds for Interpolation and Normals on Triangulated Surfaces and Manifolds. arXiv:1911.03424, 2019. https://arxiv.org/abs/1911.03424
17. Jonathan Richard Shewchuk. Better Sampling Bounds for Restricted Delaunay Triangulations and a Star-Shaped Property for Restricted Voronoi Cells. arXiv:2603.19826, 2026. https://arxiv.org/abs/2603.19826