Vietoris–Rips complex

In topology, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is an abstract simplicial complex that can be defined from any metric space "M" and distance δ by forming a simplex for every finite set of points that has diameter at most δ. That is, it is a family of finite subsets of "M", in which we think of a subset of "k" points as forming a ("k" − 1)-dimensional simplex (an edge for two points, a triangle for three points, a tetrahedron for four points, etc.); if a finite set "S" has the property that the distance between every pair of points in "S" is at most δ, then we include "S" as a simplex in the complex.

History

The Vietoris–Rips complex was originally called the Vietoris complex, for Leopold Vietoris, who introduced it as a means of extending homology theory from simplicial complexes to metric spaces. [harvtxt|Vietoris|1927; harvtxt|Lefschetz|1942; harvtxt|Hausmann|1995; harvtxt|Reitberger|2002.] After Eliyahu Rips applied the same complex to the study of hyperbolic groups, its use was popularized by harvtxt|Gromov|1987, who called it the Rips complex. [harvtxt|Hausmann|1995; harvtxt|Reitberger|2002.] . The name "Vietoris–Rips complex" is due to harvtxt|Hausmann|1995. [harvtxt|Reitberger|2002.]

Relation to Čech complex

The Vietoris–Rips complex is closely related to the Čech complex of a set of balls, which has a simplex for every finite subset of balls with nonempty intersection: in a geodesically convex space "Y", the Vietoris–Rips complex of any subspace "X" ⊂ "Y" for distance δ has the same points and edges as the Čech complex of the set of balls of radius δ/2 in "Y" that are centered at the points of "X". However, unlike the Čech complex, the Vietoris–Rips complex of "X" depends only on the intrinsic geometry of "X", and not on any embedding of "X" into some larger space.

As an example, consider the uniform metric space "M"₃ consisting of three points, each at unit distance from each other. The Vietoris–Rips complex of "M"₃, for δ = 1, includes a simplex for every subset of points in "M"₃, including a triangle for "M"₃ itself. If we embed "M"₃ as an equilateral triangle in the Euclidean plane, then the Čech complex of the radius-1/2 balls centered at the points of "M"₃ would contain all other simplexes of the Vietoris–Rips complex but would not contain this triangle, as there is no point of the plane contained in all three balls. However, if "M"₃ is instead embedded into a metric space that contains a fourth point at distance 1/2 from each of the three points of "M"₃, the Čech complex of the radius-1/2 balls in this space would contain the triangle. Thus, the Čech complex of fixed-radius balls centered at "M"₃ differs depending on which larger space "M"₃ might be embedded into, while the Vietoris–Rips complex remains unchanged.

If any metric space "X" is embedded in an injective metric space "Y", the Vietoris–Rips complex for distance δ and "X" coincides with the Čech complex of the balls of radius δ/2 centered at the points of "X" in "Y". Thus, the Vietoris–Rips complex of any metric space "M" equals the Čech complex of a system of balls in the tight span of "M".

Relation to unit disk graphs and clique complexes

The Vietoris–Rips complex for δ = 1 contains an edge for every pair of points that are at unit distance or less in the given metric space. As such, its 1-skeleton is the unit disk graph of its points. It contains a simplex for every clique in the unit disk graph, so it is the clique complex or flag complex of the unit disk graph. [harvtxt|Chambers|Erickson|Worah|2007.] More generally, the clique complex of any graph "G" is a Vietoris–Rips complex for the metric space having as points the vertices of "G" and having as its distances the lengths of the shortest paths in "G".

Other results

If "M" is a closed Riemannian manifold, then for sufficiently small values of δ the Vietoris–Rips complex of "M", or of spaces sufficiently close to "M", is homotopy equivalent to "M" itself. [harvtxt|Hausmann|1995, harvtxt|Latschev|2001.]

harvtxt|Chambers|Erickson|Worah|2007 describe efficient algorithms for determining whether a given cycle is contractible in the Rips complex of any finite point set in the Euclidean plane.

Applications

As with unit disk graphs, the Vietoris–Rips complex has been applied in computer science to model the topology of ad-hoc wireless communication networks. One advantage of the Vietoris–Rips complex in this application is that it can be determined only from the distances between the communication nodes, without having to infer their exact physical locations. A disadvantage is that, unlike the Čech complex, the Vietoris–Rips complex does not directly provide information about gaps in communication coverage, but this flaw can be ameliorated by sandwiching the Čech complex between two Vietoris–Rips complexes for different values of δ. [harvtxt|de Silva|Ghrist|2006, harvtxt|Muhammad|Jadbabaie|2007.]

Vietoris–Rips complexes have also been applied for feature-extraction in digital image data; in this application, the complex is built from a high-dimensional metric space in which the points represent low-level image features. [harvtxt|Carlsson|Carlsson|de Silva|2006.]

Notes

References

*citation
first1 = E. | last1 = Carlsson
first2 = G. | last2 = Carlsson
first3 = V. | last3 = de Silva
title = An algebraic topological method for feature identification
journal = Int. J. Comput. Geom. Appl.
volume = 16 | issue = 4 | pages = 291–314 | year = 2006.

*citation
first1 = Erin W. | last1 = Chambers
first2 = Jeff | last2 = Erickson
first3 = Pratik | last3 = Worah
title = Testing contractability in planar Rips complexes
year = 2007
url = http://granmapa.cs.uiuc.edu/~jeffe/pubs/ripscon.html

*citation
first1 = Frédéric | last1 = Chazal
first2 = Steve | last2 = Oudot
title = Towards Persistence-Based Reconstruction in Euclidean Spaces
year = 2008
journal = ACM Symposium on Computational Geometry
doi = 10.1145/1377676.1377719
url = http://math.u-bourgogne.fr/IMB/chazal/RR-6391.pdf

*citation
first1 = V. | last1 = de Silva
first2 = R. | last2 = Ghrist
title = Coordinate-free coverage in sensor networks with controlled boundaries via homology
journal = The International Journal of Robotics Research
volume = 25 | issue = 12 | year = 2006 | pages = 1205–1222
doi = 10.1177/0278364906072252.

*citation
last = Gromov | first = M. | authorlink = Mikhail Gromov
contribution = Hyperbolic groups
title = Essays in group theory
pages = 75–263 | year = 1987
series = Mathematical Sciences Research Institute Publications
volume = 8
publisher = Springer-Verlag.

*citation
first = J.-C. | last = Hausmann
contribution = On the Vietoris–Rips complexes and a cohomology theory for metric spaces
title = Prospects in Topology: Proceedings of a conference in honour of William Browder
pages = 175–188 | year = 1995
publisher = Princeton Univ. Press
series = Annals of Mathematics Studies
volume = 138
id = MathSciNet | id = 1368659.

*citation
first = S.
last = Lefschetz
title = Algebraic Topology
publisher = Amer. Math. Soc.
location = New York
year = 1942
id = MathSciNet | id = 0007093
pages = 271.

*citation
contribution = Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians
first1 = A. | last1 = Muhammad
first2 = A. | last2 = Jadbabaie
editor-first = Oliver | editor-last = Broch
title = Robotics: Science and Systems
publisher = MIT Press
year = 2007
contribution-url = http://www.seas.upenn.edu/~jadbabai/papers/RSS_FINAL.pdf.

*citation
first = Heinrich | last = Reitberger
title = Leopold Vietoris (1891–2002)
journal = Notices of the American Mathematical Society
volume = 49
issue = 20
year = 2002
url = http://www.ams.org/notices/200210/fea-vietoris.pdf.

*citation
first = L. | last = Vietoris | authorlink = Leopold Vietoris
title = Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen
journal = Mathematische Annalen
volume = 97 | issue = 1 | year = 1927 | pages = 454–472
doi = 10.1007/BF01447877.