Improved Topological Approximations by Digitization

12/12/2018

∙

by   Aruni Choudhary, et al.

∙

0

∙

share

Č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 R^d, for ϵ∈(0,1]. Our approximation has a total size of n(1/ϵ)^O(d) 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 n(1/ϵ)^O(d) 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.