التفاصيل البيبلوغرافية
| العنوان: |
Sparse Higher Order Čech Filtrations. |
| المؤلفون: |
Buchet, Mickaël1 (AUTHOR) mickael.buchet@m4x.org, B Dornelas, Bianca1 (AUTHOR) contact@bdornelas.com, Kerber, Michael1 (AUTHOR) kerber@tugraz.at |
| المصدر: |
Journal of the ACM. Aug2024, Vol. 71 Issue 4, p1-23. 23p. |
| مصطلحات موضوعية: |
*DATA analysis, *ALGORITHMS, SEQUENCE spaces, TOPOLOGY |
| مستخلص: |
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] |
|
Copyright of Journal of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |