Back to Search
Start Over
Sparse Higher Order Čech Filtrations.
- Source :
- Journal of the ACM; Aug2024, Vol. 71 Issue 4, p1-23, 23p
- Publication Year :
- 2024
-
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. Our method also extends to the multicover bifiltration, composed of the k-fold filtrations for several values of k, with the same size and complexity bounds. [ABSTRACT FROM AUTHOR]
- Subjects :
- SEQUENCE spaces
DATA analysis
TOPOLOGY
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00045411
- Volume :
- 71
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Journal of the ACM
- Publication Type :
- Academic Journal
- Accession number :
- 179038769
- Full Text :
- https://doi.org/10.1145/3666085