2026-07-26T01:26:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23163 2025-10-02T12:41:37Z ddc:004 open_access

When Alpha-Complexes Collapse onto Codimension-1 Submanifolds Attali, Dominique Clémot, Mattéo Dornelas, Bianca B. Lieutier, André Submanifold reconstruction triangulation abstract simplicial complexes collapses convexity Given a finite set of points P sampling an unknown smooth surface ℳ ⊆ ℝ³, our goal is to triangulate ℳ based solely on P. Assuming ℳ is a smooth orientable submanifold of codimension 1 in ℝ^d, we introduce a simple algorithm, Naive Squash, which simplifies the α-complex of P by repeatedly applying a new type of collapse called vertical relative to ℳ. Naive Squash also has a practical version that does not require knowledge of ℳ. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of ℳ. We provide a bound on the angle formed by triangles in the α-complex with ℳ, yielding sampling conditions on P that are competitive with existing literature for smooth surfaces embedded in ℝ³, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of P triangulates ℳ when ℳ is a smooth surface in ℝ³ under weaker conditions than existing ones. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dominique Attali and Mattéo Clémot and Bianca B. Dornelas and André Lieutier 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.11 urn:nbn:de:0030-drops-231630 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode