Search Results

Documents authored by Stephenson, Elizabeth


Document
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
Media Exposition
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}
}
Document
Media Exposition
A Cautionary Tale: Burning the Medial Axis Is Unstable (Media Exposition)

Authors: Erin Chambers, Christopher Fillmore, Elizabeth Stephenson, and Mathijs Wintraecken

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities various prunings of the medial axis have been proposed. Here, we examine one type of pruning, called burning. Because of the good experimental results, it was hoped that the burning method of simplifying the medial axis would be stable. In this work we show a simple example that dashes such hopes based on Bing’s house with two rooms, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible.

Cite as

Erin Chambers, Christopher Fillmore, Elizabeth Stephenson, and Mathijs Wintraecken. A Cautionary Tale: Burning the Medial Axis Is Unstable (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.SoCG.2022.66,
  author =	{Chambers, Erin and Fillmore, Christopher and Stephenson, Elizabeth and Wintraecken, Mathijs},
  title =	{{A Cautionary Tale: Burning the Medial Axis Is Unstable}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{66:1--66:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.66},
  URN =		{urn:nbn:de:0030-drops-160744},
  doi =		{10.4230/LIPIcs.SoCG.2022.66},
  annote =	{Keywords: Medial axis, Collapse, Pruning, Burning, Stability}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail