---
_id: '13048'
abstract:
- lang: eng
  text: 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 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 (dH) sense then the (λ,α)-medial axes of K and K′ are close as
    metric spaces, that is the Gromov-Hausdorff distance (dGH) between the two is
    1/4-Hölder in the sense that dGH (axλα(K),axλα(K′)) ≲ dH(K,K′)1/4. The Hausdorff
    distance between the two medial axes is also bounded, by dH (axλα(K),λα(K′)) ≲
    dH(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.
acknowledgement: "We are greatly indebted to Erin Chambers for posing a number of
  questions that eventually led to this paper. We would also like to thank the other
  organizers of the workshop on ‘Algorithms\r\nfor the medial axis’. We are also indebted
  to Tatiana Ezubova for helping with the search for and translation of Russian literature.
  The second author thanks all members of the Edelsbrunner and Datashape groups for
  the atmosphere in which the research was conducted.\r\nThe research leading to these
  results has received funding from the European Research Council (ERC) under the
  European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement
  No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions).
  Supported by the European Union’s Horizon 2020 research and innovation programme
  under the Marie Skłodowska-Curie grant agreement No. 754411. The Austrian science
  fund (FWF) M-3073."
article_processing_charge: No
arxiv: 1
author:
- first_name: André
  full_name: Lieutier, André
  last_name: Lieutier
- first_name: Mathijs
  full_name: Wintraecken, Mathijs
  id: 307CFBC8-F248-11E8-B48F-1D18A9856A87
  last_name: Wintraecken
  orcid: 0000-0002-7472-2220
citation:
  ama: 'Lieutier A, Wintraecken M. Hausdorff and Gromov-Hausdorff stable subsets of
    the medial axis. In: <i>Proceedings of the 55th Annual ACM Symposium on Theory
    of Computing</i>. Association for Computing Machinery; 2023:1768-1776. doi:<a
    href="https://doi.org/10.1145/3564246.3585113">10.1145/3564246.3585113</a>'
  apa: 'Lieutier, A., &#38; Wintraecken, M. (2023). Hausdorff and Gromov-Hausdorff
    stable subsets of the medial axis. In <i>Proceedings of the 55th Annual ACM Symposium
    on Theory of Computing</i> (pp. 1768–1776). Orlando, FL, United States: Association
    for Computing Machinery. <a href="https://doi.org/10.1145/3564246.3585113">https://doi.org/10.1145/3564246.3585113</a>'
  chicago: Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff
    Stable Subsets of the Medial Axis.” In <i>Proceedings of the 55th Annual ACM Symposium
    on Theory of Computing</i>, 1768–76. Association for Computing Machinery, 2023.
    <a href="https://doi.org/10.1145/3564246.3585113">https://doi.org/10.1145/3564246.3585113</a>.
  ieee: A. Lieutier and M. Wintraecken, “Hausdorff and Gromov-Hausdorff stable subsets
    of the medial axis,” in <i>Proceedings of the 55th Annual ACM Symposium on Theory
    of Computing</i>, Orlando, FL, United States, 2023, pp. 1768–1776.
  ista: 'Lieutier A, Wintraecken M. 2023. Hausdorff and Gromov-Hausdorff stable subsets
    of the medial axis. Proceedings of the 55th Annual ACM Symposium on Theory of
    Computing. STOC: Symposium on Theory of Computing, 1768–1776.'
  mla: Lieutier, André, and Mathijs Wintraecken. “Hausdorff and Gromov-Hausdorff Stable
    Subsets of the Medial Axis.” <i>Proceedings of the 55th Annual ACM Symposium on
    Theory of Computing</i>, Association for Computing Machinery, 2023, pp. 1768–76,
    doi:<a href="https://doi.org/10.1145/3564246.3585113">10.1145/3564246.3585113</a>.
  short: A. Lieutier, M. Wintraecken, in:, Proceedings of the 55th Annual ACM Symposium
    on Theory of Computing, Association for Computing Machinery, 2023, pp. 1768–1776.
conference:
  end_date: 2023-06-23
  location: Orlando, FL, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2023-06-20
date_created: 2023-05-22T08:02:02Z
date_published: 2023-06-02T00:00:00Z
date_updated: 2023-05-22T08:15:19Z
day: '02'
department:
- _id: HeEd
doi: 10.1145/3564246.3585113
ec_funded: 1
external_id:
  arxiv:
  - '2303.04014'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2303.04014
month: '06'
oa: 1
oa_version: Preprint
page: 1768-1776
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
- _id: fc390959-9c52-11eb-aca3-afa58bd282b2
  grant_number: M03073
  name: Learning and triangulating manifolds via collapses
publication: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
publication_identifier:
  isbn:
  - '9781450399135'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: Hausdorff and Gromov-Hausdorff stable subsets of the medial axis
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...