2016/01/12 by Choudhary, Aruni, Kerber, Michael, Raghvendra, Sharath
#55U99 #68W01 #68W25 #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1601.02732
Classical methods to model topological properties of point clouds, such as the Vietoris-Rips complex, suffer from the combinatorial explosion of complex sizes. We propose a novel technique to approximate a multi-scale filtration of the Rips complex with improved bounds for size: precisely, for n points in ℝd, we obtain a O(d)-approximation with at most n2O(d log k) simplices of dimension k or lower. In conjunction with dimension reduction techniques, our approach yields a O(polylog (n))-approximation of size nO(1) for Rips filtrations on arbitrary metric spaces. This result stems from high-dimensional lattice geometry and exploits properties of the permutahedral lattice, a well-studied structure in discrete geometry. Building on the same geometric concept, we also present a lower bound result on the size of an approximate filtration: we construct a point set for which every (1+ε)-approximation of the Čech filtration has to contain nΩ(loglog n) features, provided that ε