2 Search Results for "Rolle, Alexander"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.20
Sparse Higher Order Čech Filtrations

Authors: Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
For a finite set of balls of radius r, the k-fold cover is the space covered by at least k balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the k-fold filtration of the centers. For k = 1, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger k, it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the k-fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case k = 1, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points.
Cite as

Mickaël Buchet, Bianca B. Dornelas, and Michael Kerber. Sparse Higher Order Čech Filtrations. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2023.20,
  author =	{Buchet, Micka\"{e}l and B. Dornelas, Bianca and Kerber, Michael},
  title =	{{Sparse Higher Order \v{C}ech Filtrations}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.20},
  URN =		{urn:nbn:de:0030-drops-178709},
  doi =		{10.4230/LIPIcs.SoCG.2023.20},
  annote =	{Keywords: Sparsification, k-fold cover, Higher order \v{C}ech complexes}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.58
The Degree-Rips Complexes of an Annulus with Outliers

Authors: Alexander Rolle

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

Abstract
The degree-Rips bifiltration is the most computable of the parameter-free, density-sensitive bifiltrations in topological data analysis. It is known that this construction is stable to small perturbations of the input data, but its robustness to outliers is not well understood. In recent work, Blumberg-Lesnick prove a result in this direction using the Prokhorov distance and homotopy interleavings. Based on experimental evaluation, they argue that a more refined approach is desirable, and suggest the framework of homology inference. Motivated by these experiments, we consider a probability measure that is uniform with high density on an annulus, and uniform with low density on the disc inside the annulus. We compute the degree-Rips complexes of this probability space up to homotopy type, using the Adamaszek-Adams computation of the Vietoris-Rips complexes of the circle. These degree-Rips complexes are the limit objects for the Blumberg-Lesnick experiments. We argue that the homology inference approach has strong explanatory power in this case, and suggest studying the limit objects directly as a strategy for further work.
Cite as

Alexander Rolle. The Degree-Rips Complexes of an Annulus with Outliers. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rolle:LIPIcs.SoCG.2022.58,
  author =	{Rolle, Alexander},
  title =	{{The Degree-Rips Complexes of an Annulus with Outliers}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{58:1--58:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.58},
  URN =		{urn:nbn:de:0030-drops-160664},
  doi =		{10.4230/LIPIcs.SoCG.2022.58},
  annote =	{Keywords: multi-parameter persistent homology, stability, homology inference}
}
  • Refine by Author
  • 1 B. Dornelas, Bianca
  • 1 Buchet, Mickaël
  • 1 Kerber, Michael
  • 1 Rolle, Alexander

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Theory of computation → Computational complexity and cryptography

  • Refine by Keyword
  • 1 Higher order Čech complexes
  • 1 Sparsification
  • 1 homology inference
  • 1 k-fold cover
  • 1 multi-parameter persistent homology
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact