Implicit Manifold Reconstruction

• Published in: Discrete & computational geometry 2019-10, Vol.62 (3), p.700-742
• Main Authors: Cheng, Siu-Wing, Chiu, Man-Kwun
• Format: Article
• Language: English
• Subjects: Combinatorics; Computational Mathematics and Numerical Analysis; Manifolds (mathematics); Mathematics; Mathematics and Statistics; Metric space; Operators (mathematics)
• ISSN: 0179-5376; 1432-0444
• DOI: 10.1007/s00454-019-00095-w

Let M ⊂ R d be a compact, smooth and boundaryless manifold with dimension m and unit reach. We show how to construct a function φ : R d → R d - m from a uniform ( ε , κ ) -sample P of M that offers several guarantees. Let Z φ denote the zero set of φ . Let M ^ denote the set of points at distance ε or less from M . There exists ε 0 ∈ ( 0 , 1 ) that decreases as d increases such that if ε ≤ ε 0 , the following guarantees hold. First, Z φ ∩ M ^ is a faithful approximation of M in the sense that Z φ ∩ M ^ is homeomorphic to M , the Hausdorff distance between Z φ ∩ M ^ and M is O ( m 5 / 2 ε 2 ) , and the normal spaces at nearby points in Z φ ∩ M ^ and M make an angle O ( m 2 κ ε ) . Second, φ has local support; in particular, the value of φ at a point is affected only by sample points in P that lie within a distance of O ( m ε ) . Third, we give a projection operator that only uses sample points in P at distance O ( m ε ) from the initial point. The projection operator maps any initial point near P onto Z φ ∩ M ^ in the limit by repeated applications.