When alpha-complexes collapse onto codimension-1 submanifolds

Abstract

Given a finite set of points $P$ sampling an unknown smooth surface $\mathcal{M}\subseteq {\mathbb{R}}^3$, our goal is to triangulate $\mathcal{M}$ based solely on $P$. Assuming $\mathcal{M}$ is a smooth orientable submanifold of codimension 1 in ${\mathbb{R}}^d$, we introduce a simple algorithm, Naive Squash, which simplifies the $\hat{I}\pm$-complex of $P$ by repeatedly applying a new type of collapse called vertical relative to $\mathcal{M}$. Naive Squash also has a practical version that does not require knowledge of $\mathcal{M}$. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of $\mathcal{M}$. We provide a bound on the angle formed by triangles in the $\hat{I}\pm$-complex with $\mathcal{M}$, yielding sampling conditions on $P$ that are competitive with existing literature for smooth surfaces embedded in ${\mathbb{R}}^3$, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of $P$ triangulates $\mathcal{M}$ when $\mathcal{M}$ is a smooth surface in ${\mathbb{R}}^3$ under weaker conditions than existing ones.

56 pages, 24 figures