2024/08/29 by Michael Lesnick, Lesnick, Michael, Kenneth McCabe +1 · 1 citation
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer Graphics and Visualization Techniques #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2408.16716
openalex publication_date 2024/08/29 · openalex created_date 2024/09/22 · openalex updated_date 2026/07/28
The Vietoris-Rips filtration, the standard filtration on metric data in topological data analysis, is notoriously sensitive to outliers. Sheehy's subdivision-Rips bifiltration SR(-) is a density-sensitive refinement that is robust to outliers in a strong sense, but whose 0-skeleton has exponential size. For X a finite metric space of constant doubling dimension and fixed ε>0, we construct a (1+ε)-homotopy interleaving approximation of SR(X) whose k-skeleton has size O(|X|k+2). For k≥ 1 constant, the k-skeleton can be computed in time O(|X|k+3).