Implicit Manifold Reconstruction

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