Abstract
Čech complexes are useful simplicial complexes for computing and analyzing topological features of data that lies in Euclidean space. Unfortunately, computing these complexes becomes prohibitively expensive for large-sized data sets even for medium-to-low dimensional data. We present an approximation scheme for (1 + ε)-approximating the topological information of the Čech complexes for n points in Rd, for ε ∈ (0, 1]. Our approximation has a total size of [MATH HERE] for constant dimension d, improving all the currently available (1 + ε)-approximation schemes of simplicial filtrations in Euclidean space. Perhaps counter-intuitively, we arrive at our result by adding additional [MATH HERE] sample points to the input. We achieve a bound that is independent of the spread of the point set by pre-identifying the scales at which the Čech complexes changes and sampling accordingly.
Originalsprache | englisch |
---|---|
Titel | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 |
Erscheinungsort | Philadelphia |
Herausgeber (Verlag) | SIAM - Society of Industrial and Applied Mathematics |
Seiten | 2675-2688 |
Publikationsstatus | Veröffentlicht - 2019 |
Veranstaltung | 30th Annual ACM-SIAM Symposium on Discrete Algorithms - San Diego, USA / Vereinigte Staaten Dauer: 6 Jan. 2019 → 9 Jan. 2019 |
Konferenz
Konferenz | 30th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Kurztitel | SODA '19 |
Land/Gebiet | USA / Vereinigte Staaten |
Ort | San Diego |
Zeitraum | 6/01/19 → 9/01/19 |
Fields of Expertise
- Information, Communication & Computing