Search Results

Documents authored by Dal Poz Kouřimská, Hana

Document
DOI: 10.4230/LIPIcs.SoCG.2024.11
Tight Bounds for the Learning of Homotopy à la Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds

Authors: Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
In this article we extend and strengthen the seminal work by Niyogi, Smale, and Weinberger on the learning of the homotopy type from a sample of an underlying space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds with positive reach embedded in ℝ^d. We extend their results in the following ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with lower bounded sectional curvature. - In both types of ambient spaces, we study sets of positive reach - a significantly more general setting than C² manifolds - as well as general manifolds of positive reach. - The sample P of a set (or a manifold) 𝒮 of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and 𝒮. We provide tight bounds in terms of ε and δ, that guarantee that there exists a parameter r such that the union of balls of radius r centred at the sample P deformation-retracts to 𝒮. We exhibit their tightness by an explicit construction. We carefully distinguish the roles of δ and ε. This is not only essential to achieve tight bounds, but also sensible in practical situations, since it allows one to adapt the bound according to sample density and the amount of noise present in the sample separately.
Cite as

Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. Tight Bounds for the Learning of Homotopy à la Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2024.11,
  author =	{Attali, Dominique and Dal Poz Kou\v{r}imsk\'{a}, Hana and Fillmore, Christopher and Ghosh, Ishika and Lieutier, Andr\'{e} and Stephenson, Elizabeth and Wintraecken, Mathijs},
  title =	{{Tight Bounds for the Learning of Homotopy \`{a} la Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.11},
  URN =		{urn:nbn:de:0030-drops-199565},
  doi =		{10.4230/LIPIcs.SoCG.2024.11},
  annote =	{Keywords: Homotopy, Inference, Sets of positive reach}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.69
The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms

Authors: Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let 𝒮 ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set 𝒮. Consider the space of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant. The map from this space of diffeomorphisms (endowed with a Banach norm) to the space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping a diffeomorphism F to the closure of the medial axis of F(𝒮), is Lipschitz. This extends a previous stability result of Chazal and Soufflet on the stability of the medial axis of C² manifolds under C² ambient diffeomorphisms.
Cite as

Hana Dal Poz Kouřimská, André Lieutier, and Mathijs Wintraecken. The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 69:1-69:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dalpozkourimska_et_al:LIPIcs.SoCG.2024.69,
  author =	{Dal Poz Kou\v{r}imsk\'{a}, Hana and Lieutier, Andr\'{e} and Wintraecken, Mathijs},
  title =	{{The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{69:1--69:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.69},
  URN =		{urn:nbn:de:0030-drops-200149},
  doi =		{10.4230/LIPIcs.SoCG.2024.69},
  annote =	{Keywords: Medial axis, Hausdorff distance, Lipschitz continuity}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2024.87
The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition)

Authors: Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
In our companion paper "Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds" we gave optimal bounds (in terms of the two one-sided Hausdorff distances) on a sample P of an input shape 𝒮 (either manifold or general set with positive reach) such that one can infer the homotopy of 𝒮 from the union of balls with some radius centred at P, both in Euclidean space and in a Riemannian manifold of bounded curvature. The construction showing the optimality of the bounds is not straightforward. The purpose of this video is to visualize and thus elucidate said construction in the Euclidean setting.
Cite as

Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. The Ultimate Frontier: An Optimality Construction for Homotopy Inference (Media Exposition). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 87:1-87:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{attali_et_al:LIPIcs.SoCG.2024.87,
  author =	{Attali, Dominique and Dal Poz Kou\v{r}imsk\'{a}, Hana and Fillmore, Christopher and Ghosh, Ishika and Lieutier, Andr\'{e} and Stephenson, Elizabeth and Wintraecken, Mathijs},
  title =	{{The Ultimate Frontier: An Optimality Construction for Homotopy Inference}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{87:1--87:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.87},
  URN =		{urn:nbn:de:0030-drops-200325},
  doi =		{10.4230/LIPIcs.SoCG.2024.87},
  annote =	{Keywords: Homotopy, Inference, Sets of positive reach}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact