Vietoris-Rips complexes of planar point sets

DOI10.1007/S00454-009-9209-8zbMATH Open1231.05306arXiv0712.0395OpenAlexW1980200998MaRDI QIDQ977181FDOQ977181

Jeff Erickson, Vin de Silva, Erin W. Chambers, Robert Ghrist

Publication date: 21 June 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: Fix a finite set of points in Euclidean $n$-space $eu{c}^n$, thought of as a point-cloud sampling of a certain domain $Dsubseteu{c}^n$. The Rips complex is a combinatorial simplicial complex based on proximity of neighbors that serves as an easily-computed but high-dimensional approximation to the homotopy type of $D$. There is a natural ``shadow projection map from the Rips complex to $eu{c}^n$ that has as its image a more accurate $n$-dimensional approximation to the homotopy type of $D$. We demonstrate that this projection map is 1-connected for the planar case $n=2$. That is, for planar domains, the Rips complex accurately captures connectivity and fundamental group data. This implies that the fundamental group of a Rips complex for a planar point set is a free group. We show that, in contrast, introducing even a small amount of uncertainty in proximity detection leads to `quasi'-Rips complexes with nearly arbitrary fundamental groups. This topological noise can be mitigated by examining a pair of quasi-Rips complexes and using ideas from persistent topology. Finally, we show that the projection map does not preserve higher-order topological data for planar sets, nor does it preserve fundamental group data for point sets in dimension larger than three.

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

Recommendations

• On homotopy types of Euclidean Rips complexes
• Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes
• Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes
• Linear-size approximations to the Vietoris-Rips filtration
• The Vietoris-Rips complexes of a circle

zbMATH Keywords

topologyRips complexquasi-Rips complex

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Finding the homology of submanifolds with high confidence from random samples
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the local behavior of spaces of natural images
• Coverage in sensor networks via persistent homology
• Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology
• PERSISTENCE BARCODES FOR SHAPES
• Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians
• AN ALGEBRAIC TOPOLOGICAL METHOD FOR FEATURE IDENTIFICATION
• Testing contractibility in planar rips complexes
• Local approximation schemes for topology control

Cited In (19)

• Distributed computation of coverage in sensor networks by homological methods
• Extremal Betti numbers of Vietoris-Rips complexes
• On homotopy types of Euclidean Rips complexes
• Mayer-Vietoris sequences and coverage problems in sensor networks
• Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes
• Bestvina–Brady discrete Morse theory and Vietoris–Rips complexes
• On the Reconstruction of Geodesic Subspaces of ℝN
• Title not available (Why is that?)
• The Persistent Homology of Cyclic Graphs
• On Vietoris-Rips complexes of hypercube graphs
• Geometric Approaches to Persistent Homology
• Vietoris-Rips complexes of metric spaces near a metric graph
• Geometry-driven collapses for converting a Čech complex into a triangulation of a nicely triangulable shape
• Random geometric complexes
• Footprints of geodesics in persistent homology
• The Vietoris-Rips complexes of a circle
• Metric thickenings of Euclidean submanifolds
• On Vietoris–Rips Complexes (with Scale 3) of Hypercube Graphs
• Complexity of simplicial homology and independence complexes of chordal graphs

This page was built for publication: Vietoris-Rips complexes of planar point sets

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