Lune

STOC2023Top-tier venue

Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial Axis

Andrรฉ Lieutier, Mathijs Wintraecken

Abstract

In this paper we introduce a pruning of the medial axis called the (๐œ†, ๐›ผ)-medial axis (ax ๐›ผ ๐œ† ). We prove that the (๐œ†, ๐›ผ)-medial axis of a set ๐พ is stable in a Gromov-Hausdorff sense under weak assumptions. More formally we prove that if ๐พ and ๐พ โ€ฒ are close in the Hausdorff (๐‘‘ ๐ป ) sense then the (๐œ†, ๐›ผ)-medial axes of ๐พ and ๐พ โ€ฒ are close as metric spaces, that is the Gromov-Hausdorff distance (๐‘‘ ๐บ๐ป ) between the two is 1 4 -Hรถlder in the sense that ๐‘‘ ๐บ๐ป (ax ๐›ผ ๐œ† (๐พ), ax ๐›ผ ๐œ† (๐พ โ€ฒ )) โ‰ฒ ๐‘‘ ๐ป (๐พ, ๐พ โ€ฒ ) 1/4 . The Hausdorff distance between the two medial axes is also bounded, by ๐‘‘ ๐ป (ax ๐›ผ ๐œ† (๐พ), ax ๐›ผ ๐œ† (๐พ โ€ฒ )) โ‰ฒ ๐‘‘ ๐ป (๐พ, ๐พ โ€ฒ ) 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper ยท related work

Get the answer

Free to start. No credit card required.

Related papers

  1. CORE-Sketch: On Exact Computation of Median Absolute Deviation with Limited SpaceHaoquan Guan, Ziling Chen, Shaoxu SongVLDB 2023 ยท 1 citation
  2. Private Geometric Median in Nearly-Linear TimeSyamantak Kumar, Daogao Liu, Kevin Tian, Chutong YangNeurIPS 2025 ยท 1 citation
  3. -Functions Piecewise-linear Approximation from Noisy and Hermite DataMarc AlexaSIGGRAPH 2022 ยท 1 citation
  4. Structural MAT: Clean and Scalable Medial Axis Simplification via Explicit Surface CorrespondencePengfei Wang, Shuangmin Chen, Dong-Ming Yan, Ying He et al.SIGGRAPH 2026
  5. Computing Approximate Centerpoints in Polynomial TimeYeshwanth CherapanamjeriFOCS 2024 ยท 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines