2019/11/08 by Marc Khoury, Khoury, Marc, Jonathan Richard Shewchuk +1
Computer Science · Engineering · #3D Shape Modeling and Analysis #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1911.03424
openalex publication_date 2019/11/08 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
How good is a triangulation as an approximation of a smooth curved surface or\nmanifold? We provide bounds on the em interpolation error, the error in the\nposition of the surface, and the em normal error, the error in the normal\nvectors of the surface, as approximated by a piecewise linearly triangulated\nsurface whose vertices lie on the original, smooth surface. The interpolation\nerror is the distance from an arbitrary point on the triangulation to the\nnearest point on the original, smooth manifold, or vice versa. The normal error\nis the angle separating the vector (or space) normal to a triangle from the\nvector (or space) normal to the smooth manifold (measured at a suitable point\nnear the triangle). We also study the em normal variation, the angle\nseparating the normal vectors (or normal spaces) at two different points on a\nsmooth manifold. Our bounds apply to manifolds of any dimension embedded in\nEuclidean spaces of any dimension, and our interpolation error bounds apply to\nsimplices of any dimension, although our normal error bounds apply only to\ntriangles. These bounds are expressed in terms of the sizes of suitable medial\nballs (the em empty ball size or em local feature size measured at\ncertain points on the manifold), and have applications in Delaunay\ntriangulation-based algorithms for provably good surface reconstruction and\nprovably good mesh generation. Our bounds have better constants than the prior\nbounds we know of---and for several results in higher dimensions, our bounds\nare the first to give explicit constants.\n