Approximate Čech Complex in Low and High Dimensions

DOI10.1007/978-3-642-45030-3_62MaRDI QIDQ2872131zbMATH OpenOpenAlexFDO

Authors Michael Kerber, R. Sharathkumar

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.3272

Mathematics Subject Classification ID

Simplicial sets and complexes in algebraic topology (55U10) General topics in the theory of data (68P01) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: v{C}ech complexes reveal valuable topological information about point sets at a certain scale in arbitrary dimensions, but the sheer size of these complexes limits their practical impact. While recent work introduced approximation techniques for filtrations of (Vietoris-)Rips complexes, a coarser version of v{C}ech complexes, we propose the approximation of v{C}ech filtrations directly. For fixed dimensional point set $S$, we present an approximation of the v{C}ech filtration of $S$ by a sequence of complexes of size linear in the number of points. We generalize well-separated pair decompositions (WSPD) to well-separated simplicial decomposition (WSSD) in which every simplex defined on $S$ is covered by some element of WSSD. We give an efficient algorithm to compute a linear-sized WSSD in fixed dimensional spaces. Using a WSSD, we then present a linear-sized approximation of the filtration of v{C}ech complex of $S$. We also present a generalization of the known fact that the Rips complex approximates the v{C}ech complex by a factor of $sqrt2$. We define a class of complexes that interpolate between v{C}ech and Rips complexes and that, given any parameter $eps>0$, approximate the v{C}ech complex by a factor $(1+eps)$. Our complex can be represented by roughly $O(n^{lceil1/2epsceil})$ simplices without any hidden dependence on the ambient dimension of the point set. Our results are based on an interesting link between v{C}ech complex and coresets for minimum enclosing ball of high-dimensional point sets. As a consequence of our analysis, we show improved bounds on coresets that approximate the radius of the minimum enclosing ball.

Recommendations

• Finite approximations to Čech homology
• A Generalization of Ceva's Theorem to Higher Dimensions
• scientific article; zbMATH DE number 3398114
• Quasicomponents, Čech systems, and approximate systems
• Random Čech complexes on Riemannian manifolds
• scientific article; zbMATH DE number 5925307
• The Alekseevskii conjecture in low dimensions
• Random Čech complexes on manifolds with boundary
• Higher order multi-dimensional extensions of Cesàro theorem
• Čech approximation to the Brown-Gersten spectral sequence

Cited in

(17)

• Polynomial-sized topological approximations using the permutahedron
• Quantitative simplification of filtered simplicial complexes
• Improved approximate Rips filtrations with shifted integer lattices and cubical complexes
• Approximating persistent homology in Euclidean space through collapses
• Barcodes of towers and a streaming algorithm for persistent homology
• Topological data analysis of noise: uniform unimodal distributions
• The Offset Filtration of Convex Objects
• Strong Collapse for Persistence
• Computing persistent homology of flag complexes via strong collapses
• Improved approximate Rips filtrations with shifted integer lattices
• Persistent Homology of Geospatial Data: A Case Study with Voting
• Improved topological approximations by digitization
• scientific article; zbMATH DE number 7651177 (Why is no real title available?)
• Strong collapse and persistent homology
• Sparse higher order Čech filtrations
• Adaptive approximation of persistent homology
• Maximum persistent Betti numbers of Čech complexes

This page was built for publication: Approximate Čech Complex in Low and High Dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872131)