2026-07-26T16:59:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5923 2024-03-06T10:37:17Z ddc:004 open_access

Polynomial-Sized Topological Approximations Using the Permutahedron Choudhary, Aruni Kerber, Michael Raghvendra, Sharath Persistent Homology Topological Data Analysis Simplicial Approximation Permutahedron Approximation Algorithms 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 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(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 Cech filtration has to contain n^{Omega(log log n)} features, provided that epsilon < 1/(log^{1+c}n) for c in (0,1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aruni Choudhary and Michael Kerber and Sharath Raghvendra 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.31 urn:nbn:de:0030-drops-59236 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.31 eng https://creativecommons.org/licenses/by/3.0/legalcode