ausblenden:
Schlagwörter:
Computer Science, Computational Geometry, cs.CG,Mathematics, Algebraic Topology, math.AT,
Zusammenfassung:
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
$\mathbb{R}^d$, we obtain a $O(d)$-approximation with at most $n2^{O(d \log
k)}$ simplices of dimension $k$ or lower. In conjunction with dimension
reduction techniques, our approach yields a $O(\mathrm{polylog}
(n))$-approximation of size $n^{O(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+\epsilon)$-approximation of the \v{C}ech filtration has to contain
$n^{\Omega(\log\log n)}$ features, provided that $\epsilon <\frac{1}{\log^{1+c}
n}$ for $c\in(0,1)$.