2026-07-26T17:15:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7825 2024-03-06T10:41:18Z ddc:004 open_access

Improved Approximate Rips Filtrations with Shifted Integer Lattices Choudhary, Aruni Kerber, Michael Raghvendra, Sharath Persistent homology Rips filtrations Approximation algorithms Topological Data Analysis 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 R^d, we present a scheme to construct a 4.24-approximation of the multi-scale filtration of the Rips complex in the L-infinity metric, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aruni Choudhary and Michael Kerber and Sharath Raghvendra 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.28 urn:nbn:de:0030-drops-78259 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.28 eng https://creativecommons.org/licenses/by/3.0/legalcode