fbpx
Wikipedia

Vietoris–Rips complex

January 01, 1970

In topology, the Vietoris–Rips complex, also called the Vietoris complex or Rips complex, is a way of forming a topological space from distances in a set of points. It 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.

A Vietoris–Rips complex of a set of 23 points in the Euclidean plane. This complex has sets of up to four points: the points themselves (shown as red circles), pairs of points (black edges), triples of points (pale blue triangles), and quadruples of points (dark blue tetrahedrons).

History edit

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.[1] After Eliyahu Rips applied the same complex to the study of hyperbolic groups, its use was popularized by Mikhail Gromov (1987), who called it the Rips complex.[2] The name "Vietoris–Rips complex" is due to Jean-Claude Hausmann (1995).[3]

Relation to Čech complex edit

The Vietoris–Rips complex is closely related to the Čech complex (or nerve) 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 M3 consisting of three points, each at unit distance from each other. The Vietoris–Rips complex of M3, for δ = 1, includes a simplex for every subset of points in M3, including a triangle for M3 itself. If we embed M3 as an equilateral triangle in the Euclidean plane, then the Čech complex of the radius-1/2 balls centered at the points of M3 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 M3 is instead embedded into a metric space that contains a fourth point at distance 1/2 from each of the three points of M3, 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 M3 differs depending on which larger space M3 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 edit

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.[4] 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 edit

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.[5]

Chambers, Erickson & Worah (2008) 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 edit

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 δ.[6] An implementation of Vietoris–Rips complexes can be found in the TDAstats R package.[7]

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.[8]

The collection of all Vietoris–Rips complexes is a commonly applied construction in persistent homology and topological data analysis, and is known as the Rips filtration.[9]

Notes edit

  1. ^ Vietoris (1927); Lefschetz (1942); Hausmann (1995); Reitberger (2002).
  2. ^ Hausmann (1995); Reitberger (2002).
  3. ^ Reitberger (2002).
  4. ^ Chambers, Erickson & Worah (2008).
  5. ^ Hausmann (1995), Latschev (2001).
  6. ^ de Silva & Ghrist (2006), Muhammad & Jadbabaie (2007).
  7. ^ Wadhwa et al. 2018.
  8. ^ Carlsson, Carlsson & de Silva (2006).
  9. ^ Dey, Tamal K.; Shi, Dayu; Wang, Yusu (2019-01-30). "SimBa: An Efficient Tool for Approximating Rips-filtration Persistence via Simplicial Batch Collapse". ACM Journal of Experimental Algorithmics. 24: 1.5:1–1.5:16. doi:10.1145/3284360. ISSN 1084-6654. S2CID 216028146.

References edit

  • Carlsson, Erik; Carlsson, Gunnar; de Silva, Vin (2006), (PDF), International Journal of Computational Geometry and Applications, 16 (4): 291–314, doi:10.1142/S021819590600204X, S2CID 5831809, archived from the original (PDF) on 2019-03-04.
  • Chambers, Erin W.; Erickson, Jeff; Worah, Pratik (2008), "Testing contractibility in planar Rips complexes", Proceedings of the 24th Annual ACM Symposium on Computational Geometry, pp. 251–259, CiteSeerX 10.1.1.296.6424, doi:10.1145/1377676.1377721, S2CID 8072058.
  • Chazal, Frédéric; Oudot, Steve (2008), "Towards persistence-based reconstruction in euclidean spaces", Proceedings of the twenty-fourth annual symposium on Computational geometry, pp. 232–241, arXiv:0712.2638, doi:10.1145/1377676.1377719, ISBN 978-1-60558-071-5, S2CID 1020710{{citation}}: CS1 maint: date and year (link).
  • de Silva, Vin; Ghrist, Robert (2006), "Coordinate-free coverage in sensor networks with controlled boundaries via homology", The International Journal of Robotics Research, 25 (12): 1205–1222, doi:10.1177/0278364906072252, S2CID 10210836.
  • Gromov, Mikhail (1987), "Hyperbolic groups", Essays in group theory, Mathematical Sciences Research Institute Publications, vol. 8, Springer-Verlag, pp. 75–263.
  • Hausmann, Jean-Claude (1995), "On the Vietoris–Rips complexes and a cohomology theory for metric spaces", Prospects in Topology: Proceedings of a conference in honour of William Browder, Annals of Mathematics Studies, vol. 138, Princeton University Press, pp. 175–188, MR 1368659.
  • Latschev, Janko (2001), "Vietoris–Rips complexes of metric spaces near a closed Riemannian manifold", Archiv der Mathematik, 77 (6): 522–528, doi:10.1007/PL00000526, MR 1879057, S2CID 119878137.
  • Lefschetz, Solomon (1942), Algebraic Topology, New York: Amer. Math. Soc., p. 271, MR 0007093.
  • Muhammad, A.; Jadbabaie, A. (2007), "Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians" (PDF), in Broch, Oliver (ed.), Robotics: Science and Systems, MIT Press.
  • Reitberger, Heinrich (2002), "Leopold Vietoris (1891–2002)" (PDF), Notices of the American Mathematical Society, 49 (20).
  • Vietoris, Leopold (1927), "Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen", Mathematische Annalen, 97 (1): 454–472, doi:10.1007/BF01447877, S2CID 121172198.
  • Wadhwa, Raoul; Williamson, Drew; Dhawan, Andrew; Scott, Jacob (2018), "TDAstats: R pipeline for computing persistent homology in topological data analysis", Journal of Open Source Software, 3 (28): 860, Bibcode:2018JOSS....3..860R, doi:10.21105/joss.00860, PMC 7771879, PMID 33381678

January 01, 1970
vietoris, rips, complex, topology, also, called, vietoris, complex, rips, complex, forming, topological, space, from, distances, points, abstract, simplicial, complex, that, defined, from, metric, space, distance, forming, simplex, every, finite, points, that,. In topology the Vietoris Rips complex also called the Vietoris complex or Rips complex is a way of forming a topological space from distances in a set of points It is an abstract simplicial complex that can be defined from any metric space M and distance d by forming a simplex for every finite set of points that has diameter at most d 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 d then we include S as a simplex in the complex A Vietoris Rips complex of a set of 23 points in the Euclidean plane This complex has sets of up to four points the points themselves shown as red circles pairs of points black edges triples of points pale blue triangles and quadruples of points dark blue tetrahedrons Contents 1 History 2 Relation to Cech complex 3 Relation to unit disk graphs and clique complexes 4 Other results 5 Applications 6 Notes 7 ReferencesHistory editThe 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 1 After Eliyahu Rips applied the same complex to the study of hyperbolic groups its use was popularized by Mikhail Gromov 1987 who called it the Rips complex 2 The name Vietoris Rips complex is due to Jean Claude Hausmann 1995 3 Relation to Cech complex editThe Vietoris Rips complex is closely related to the Cech complex or nerve 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 d has the same points and edges as the Cech complex of the set of balls of radius d 2 in Y that are centered at the points of X However unlike the Cech 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 M3 consisting of three points each at unit distance from each other The Vietoris Rips complex of M3 for d 1 includes a simplex for every subset of points in M3 including a triangle for M3 itself If we embed M3 as an equilateral triangle in the Euclidean plane then the Cech complex of the radius 1 2 balls centered at the points of M3 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 M3 is instead embedded into a metric space that contains a fourth point at distance 1 2 from each of the three points of M3 the Cech complex of the radius 1 2 balls in this space would contain the triangle Thus the Cech complex of fixed radius balls centered at M3 differs depending on which larger space M3 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 d and X coincides with the Cech complex of the balls of radius d 2 centered at the points of X in Y Thus the Vietoris Rips complex of any metric space M equals the Cech complex of a system of balls in the tight span of M Relation to unit disk graphs and clique complexes editThe Vietoris Rips complex for d 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 4 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 editIf M is a closed Riemannian manifold then for sufficiently small values of d the Vietoris Rips complex of M or of spaces sufficiently close to M is homotopy equivalent to M itself 5 Chambers Erickson amp Worah 2008 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 editAs 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 Cech complex the Vietoris Rips complex does not directly provide information about gaps in communication coverage but this flaw can be ameliorated by sandwiching the Cech complex between two Vietoris Rips complexes for different values of d 6 An implementation of Vietoris Rips complexes can be found in the TDAstats R package 7 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 8 The collection of all Vietoris Rips complexes is a commonly applied construction in persistent homology and topological data analysis and is known as the Rips filtration 9 Notes edit Vietoris 1927 Lefschetz 1942 Hausmann 1995 Reitberger 2002 Hausmann 1995 Reitberger 2002 Reitberger 2002 Chambers Erickson amp Worah 2008 Hausmann 1995 Latschev 2001 de Silva amp Ghrist 2006 Muhammad amp Jadbabaie 2007 Wadhwa et al 2018 Carlsson Carlsson amp de Silva 2006 Dey Tamal K Shi Dayu Wang Yusu 2019 01 30 SimBa An Efficient Tool for Approximating Rips filtration Persistence via Simplicial Batch Collapse ACM Journal of Experimental Algorithmics 24 1 5 1 1 5 16 doi 10 1145 3284360 ISSN 1084 6654 S2CID 216028146 References editCarlsson Erik Carlsson Gunnar de Silva Vin 2006 An algebraic topological method for feature identification PDF International Journal of Computational Geometry and Applications 16 4 291 314 doi 10 1142 S021819590600204X S2CID 5831809 archived from the original PDF on 2019 03 04 Chambers Erin W Erickson Jeff Worah Pratik 2008 Testing contractibility in planar Rips complexes Proceedings of the 24th Annual ACM Symposium on Computational Geometry pp 251 259 CiteSeerX 10 1 1 296 6424 doi 10 1145 1377676 1377721 S2CID 8072058 Chazal Frederic Oudot Steve 2008 Towards persistence based reconstruction in euclidean spaces Proceedings of the twenty fourth annual symposium on Computational geometry pp 232 241 arXiv 0712 2638 doi 10 1145 1377676 1377719 ISBN 978 1 60558 071 5 S2CID 1020710 a href Template Citation html title Template Citation citation a CS1 maint date and year link de Silva Vin Ghrist Robert 2006 Coordinate free coverage in sensor networks with controlled boundaries via homology The International Journal of Robotics Research 25 12 1205 1222 doi 10 1177 0278364906072252 S2CID 10210836 Gromov Mikhail 1987 Hyperbolic groups Essays in group theory Mathematical Sciences Research Institute Publications vol 8 Springer Verlag pp 75 263 Hausmann Jean Claude 1995 On the Vietoris Rips complexes and a cohomology theory for metric spaces Prospects in Topology Proceedings of a conference in honour of William Browder Annals of Mathematics Studies vol 138 Princeton University Press pp 175 188 MR 1368659 Latschev Janko 2001 Vietoris Rips complexes of metric spaces near a closed Riemannian manifold Archiv der Mathematik 77 6 522 528 doi 10 1007 PL00000526 MR 1879057 S2CID 119878137 Lefschetz Solomon 1942 Algebraic Topology New York Amer Math Soc p 271 MR 0007093 Muhammad A Jadbabaie A 2007 Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians PDF in Broch Oliver ed Robotics Science and Systems MIT Press Reitberger Heinrich 2002 Leopold Vietoris 1891 2002 PDF Notices of the American Mathematical Society 49 20 Vietoris Leopold 1927 Uber den hoheren Zusammenhang kompakter Raume und eine Klasse von zusammenhangstreuen Abbildungen Mathematische Annalen 97 1 454 472 doi 10 1007 BF01447877 S2CID 121172198 Wadhwa Raoul Williamson Drew Dhawan Andrew Scott Jacob 2018 TDAstats R pipeline for computing persistent homology in topological data analysis Journal of Open Source Software 3 28 860 Bibcode 2018JOSS 3 860R doi 10 21105 joss 00860 PMC 7771879 PMID 33381678 Retrieved from https en wikipedia org w index php title Vietoris Rips complex amp oldid 1196211155, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.