Approximate Cech Complexes in Low and High Dimensions

vCech complexes reveal valuable topological information about point sets at a certain scale in arbitrary dimensions, but the sheer size of these complexes limits their practical impact. While recent work introduced approximation techniques for filtrations of (Vietoris-)Rips complexes, a coarser version of vCech complexes, we propose the approximation of vCech filtrations directly. For fixed dimensional point set S, we present an approximation of the vCech filtration of S by a sequence of complexes of size linear in the number of points. We generalize well-separated pair decompositions (WSPD) to well-separated simplicial decomposition (WSSD) in which every simplex defined on S is covered by some element of WSSD. We give an efficient algorithm to compute a linear-sized WSSD in fixed dimensional spaces. Using a WSSD, we then present a linear-sized approximation of the filtration of vCech complex of S. We also present a generalization of the known fact that the Rips complex approximates the vCech complex by a factor of √2. We define a class of complexes that interpolate between vCech and Rips complexes and that, given any parameter eps > 0, approximate the vCech complex by a factor (1+eps). Our complex can be represented by roughly O(nlceil 1/2epsrceil) simplices without any hidden dependence on the ambient dimension of the point set. Our results are based on an interesting link between vCech complex and coresets for minimum enclosing ball of high-dimensional point sets. As a consequence of our analysis, we show improved bounds on coresets that approximate the radius of the minimum enclosing ball.