Implicit Manifold Reconstruction

Let cal M subset ℝd be a compact, smooth and boundaryless manifold with dimension m and unit reach. We show how to construct a function varphi: ℝd rightarrow ℝd-m from a uniform (varepsilon,kappa)-sample P of cal M that offers several guarantees. Let Z_varphi denote the zero set of varphi. Let widehatcal M denote the set of points at distance varepsilon or less from cal M. There exists varepsilon0 ∈ (0,1) that decreases as d increases such that if varepsilon ≤ varepsilon0, the following guarantees hold. First, Z_varphi cap widehatcal M is a faithful approximation of cal M in the sense that Z_varphi cap widehatcal M is homeomorphic to cal M, the Hausdorff distance between Z_varphi cap widehatcal M and cal M is O(m5/2varepsilon2), and the normal spaces at nearby points in Z_varphi cap widehatcal M and cal M make an angle O(m2√kappavarepsilon). Second, varphi has local support; in particular, the value of varphi at a point is affected only by sample points in P that lie within a distance of O(mvarepsilon). Third, we give a projection operator that only uses sample points in P at distance O(mvarepsilon) from the initial point. The projection operator maps any initial point near P onto Z_varphi cap widehatcal M in the limit by repeated applications.