Improved Topological Approximations by Digitization

Aruni Choudhary, Michael Kerber, Sharath Raghvendra

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


Č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.
Original languageEnglish
Title of host publicationProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019
Place of PublicationPhiladelphia
PublisherSIAM - Society of Industrial and Applied Mathematics
Publication statusPublished - 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms - San Diego, United States
Duration: 6 Jan 20199 Jan 2019


Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA '19
Country/TerritoryUnited States
CitySan Diego

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Improved Topological Approximations by Digitization'. Together they form a unique fingerprint.

Cite this