max planck institut
informatik

# MPI-INF or MPI-SWS or Local Campus Event Calendar

 << Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
Title: Improved Approximate Rips Filtrations with Shifted Integer Lattices Aruni Choudhary Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1We use this to send out email in the morning. AG Audience English
Date: Tuesday, 29 August 2017 13:00 30 Minutes Saarbrücken E1 4 024
 Rips complexes are important structures for analyzing topological features of metric spaces. Unfortunately, generating these complexes constitutes an expensive task because of a combinatorial explosion in the complex size. For $n$ points in $\mathbb{R}^d$, we present a scheme to construct a $3\sqrt{2}$-approximation of the multi-scale filtration of the $L_\infty$-Rips complex, which extends to a $O(d^{0.25})$-approximation of the Rips filtration for the Euclidean case. The $k$-skeleton of the resulting approximation has a total size of $n2^{O(d\log k)}$. The scheme is based on the integer lattice and on the barycentric subdivision of the $d$-cube.
Name(s): Aruni Choudhary