3 Search Results for "Cavanna, Nicholas J."

Document

DOI: 10.4230/LIPIcs.SoCG.2025.6

A Sparse Multicover Bifiltration of Linear Size

Authors: Ángel Javier Alonso

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

The k-cover of a point cloud X of ℝ^d at radius r is the set of all those points within distance r of at least k points of X. By varying r and k we obtain a two-parameter filtration known as the multicover bifiltration. This bifiltration has received attention recently due to being choice-free and robust to outliers. However, it is hard to compute: the smallest known equivalent simplicial bifiltration has O(|X|^{d+1}) simplices. In this paper we introduce a (1+ε)-approximation of the multicover bifiltration of linear size O(|X|), for fixed d and ε. The methods also apply to the subdivision Rips bifiltration on metric spaces of bounded doubling dimension yielding analogous results.

Cite as

Ángel Javier Alonso. A Sparse Multicover Bifiltration of Linear Size. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alonso:LIPIcs.SoCG.2025.6,
  author =	{Alonso, \'{A}ngel Javier},
  title =	{{A Sparse Multicover Bifiltration of Linear Size}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.6},
  URN =		{urn:nbn:de:0030-drops-231587},
  doi =		{10.4230/LIPIcs.SoCG.2025.6},
  annote =	{Keywords: Multicover, Approximation, Sparsification, Multiparameter persistence}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.10

Steinhaus Filtration and Stable Paths in the Mapper

Authors: Dustin L. Arendt, Matthew Broussard, Bala Krishnamoorthy, Nathaniel Saul, and Amber Thrall

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

We define a new filtration called the Steinhaus filtration built from a single cover based on a generalized Steinhaus distance, a generalization of Jaccard distance. The homology persistence module of a Steinhaus filtration with infinitely many cover elements may not be q-tame, even when the covers are in a totally bounded space. While this may pose a challenge to derive stability results, we show that the Steinhaus filtration is stable when the cover is finite. We show that while the Čech and Steinhaus filtrations are not isomorphic in general, they are isomorphic for a finite point set in dimension one. Furthermore, the VR filtration completely determines the 1-skeleton of the Steinhaus filtration in arbitrary dimension. We then develop a language and theory for stable paths within the Steinhaus filtration. We demonstrate how the framework can be applied to several applications where a standard metric may not be defined but a cover is readily available. We introduce a new perspective for modeling recommendation system datasets. As an example, we look at a movies dataset and we find the stable paths identified in our framework represent a sequence of movies constituting a gentle transition and ordering from one genre to another. For explainable machine learning, we apply the Mapper algorithm for model induction by building a filtration from a single Mapper complex, and provide explanations in the form of stable paths between subpopulations. For illustration, we build a Mapper complex from a supervised machine learning model trained on the FashionMNIST dataset. Stable paths in the Steinhaus filtration provide improved explanations of relationships between subpopulations of images.

Cite as

Dustin L. Arendt, Matthew Broussard, Bala Krishnamoorthy, Nathaniel Saul, and Amber Thrall. Steinhaus Filtration and Stable Paths in the Mapper. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arendt_et_al:LIPIcs.SoCG.2025.10,
  author =	{Arendt, Dustin L. and Broussard, Matthew and Krishnamoorthy, Bala and Saul, Nathaniel and Thrall, Amber},
  title =	{{Steinhaus Filtration and Stable Paths in the Mapper}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.10},
  URN =		{urn:nbn:de:0030-drops-231625},
  doi =		{10.4230/LIPIcs.SoCG.2025.10},
  annote =	{Keywords: Cover and nerve, Jaccard distance, persistence stability, Mapper, recommender systems, explainable machine learning}
}

Document

DOI: 10.4230/LIPIcs.SOCG.2015.23

Visualizing Sparse Filtrations

Authors: Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

Over the last few years, there have been several approaches to building sparser complexes that still give good approximations to the persistent homology. In this video, we have illustrated a geometric perspective on sparse filtrations that leads to simpler proofs, more general theorems, and a more visual explanation. We hope that as these techniques become easier to understand, they will also become easier to use.

Cite as

Nicholas J. Cavanna, Mahmoodreza Jahanseir, and Donald R. Sheehy. Visualizing Sparse Filtrations. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 23-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cavanna_et_al:LIPIcs.SOCG.2015.23,
  author =	{Cavanna, Nicholas J. and Jahanseir, Mahmoodreza and Sheehy, Donald R.},
  title =	{{Visualizing Sparse Filtrations}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{23--25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.23},
  URN =		{urn:nbn:de:0030-drops-50893},
  doi =		{10.4230/LIPIcs.SOCG.2015.23},
  annote =	{Keywords: Topological Data Analysis, Simplicial Complexes, Persistent Homology}
}

Refine by Type
3 Document/PDF
2 Document/HTML

Refine by Publication Year
2 2025
1 2015

Refine by Author
1 Alonso, Ángel Javier
1 Arendt, Dustin L.
1 Broussard, Matthew
1 Cavanna, Nicholas J.
1 Jahanseir, Mahmoodreza
Show More...

Refine by Series/Journal
3 LIPIcs

Refine by Classification
1 Mathematics of computing → Topology
1 Theory of computation
1 Theory of computation → Computational geometry

Refine by Keyword
1 Approximation
1 Cover and nerve
1 Jaccard distance
1 Mapper
1 Multicover
Show More...

3 Search Results for "Cavanna, Nicholas J."

A Sparse Multicover Bifiltration of Linear Size

Abstract

Cite as

Steinhaus Filtration and Stable Paths in the Mapper

Abstract

Cite as

Visualizing Sparse Filtrations

Abstract

Cite as

Thanks for your feedback!

Could not send message