de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

#### Polynomial-Sized Topological Approximations Using The Permutahedron

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons129030

Choudhary,  Aruni
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44759

Kerber,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)

arXiv:1601.02732.pdf
(Preprint), 609KB

##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Choudhary, A., Kerber, M., & Raghvendra, S. (2016). Polynomial-Sized Topological Approximations Using The Permutahedron. Retrieved from http://arxiv.org/abs/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 $\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)$.