Hausdorff and Gromov-Hausdorff stable subsets of the medial axis
| Autor: | André Lieutier, Mathijs Wintraecken |
|---|---|
| Přispěvatelé: | Institute of Science and Technology [Klosterneuburg, Austria] (IST Austria), Université Côte d'Azur (UCA), Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), The Austrian science fund (FWF) M-3073, ACM, European Project: 339025,EC:FP7:ERC,ERC-2013-ADG,GUDHI(2014), European Project: 754411,ISTplus(2017), Chercheur indépendant, The Austrian science fund (FWF) M-3073., Auteur indépendant |
| Rok vydání: | 2023 |
| Předmět: |
Gromov-Hausdorff distance
Computational Geometry (cs.CG) FOS: Computer and information sciences computable analysis I.3.5 F.1.1 ACM: I.: Computing Methodologies/I.3: COMPUTER GRAPHICS/I.3.5: Computational Geometry and Object Modeling General Topology (math.GN) Metric Geometry (math.MG) metric stability Mathematics - Metric Geometry FOS: Mathematics Computer Science - Computational Geometry Primary: 65D18 Secondary: 54-08 51F99 55P99 Medial axis [INFO]Computer Science [cs] [MATH]Mathematics [math] Mathematics - General Topology |
| Zdroj: | STOC '23 STOC '23, ACM, Jun 2023, Orlando (Florida), United States. ⟨10.1145/3564246.3585113⟩ STOC 2023-55th Annual ACM Symposium on Theory of Computing STOC 2023-55th Annual ACM Symposium on Theory of Computing, ACM, Jun 2023, Orlando (Florida), United States. ⟨10.1145/3564246.3585113⟩ |
| DOI: | 10.48550/arxiv.2303.04014 |
| Popis: | In this paper we introduce a pruning of the medial axis called the $(\lambda,\alpha)$-medial axis ($\textrm{ax}_\lambda^\alpha $). We prove that the $(\lambda,\alpha)$-medial axis of a set $K$ is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if $K$ and $K'$ are close in the Hausdorff ($d_H$) sense then the $(\lambda,\alpha)$-medial axes of $K$ and $K'$ are close as metric spaces, that is the Gromov-Hausdorff distance ($d_{GH}$) between the two is $\frac{1}{4}$-H{\"o}lder in the sense that $d_{GH} (\textrm{ax}_\lambda^\alpha (K),\textrm{ax}_\lambda^\alpha (K')) \lesssim d_H(K,K')^{1/4}$. The Hausdorff distance between the two medial axes is also bounded, by $d_{H} (\textrm{ax}_\lambda^\alpha (K),\textrm{ax}_\lambda^\alpha (K')) \lesssim d_H(K,K')^{1/2}$. These quantified stability results provide guarantees for practical computations of medial axes from approximations. Moreover, they provide key ingredients for studying the computability of the medial axis in the context of computable analysis. Comment: Full version of a conference paper (with the same name) that was accepted for STOC'23. The conference version will be available at https://doi.org/10.1145/3564246.3585113 around the time the conference will take place |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|