User:MAHTOUT.Karim/sandbox

Un complexe de Vietoris-Rips d’un ensemble de 23 points dans le plan euclidien. Ce complexe comporte des ensembles de quatre points au maximum : les points eux-mEuclidean planeêmes (représentés par des cercles Euclidean planerouges), des paires de points (bords noirs), des triples de points (triangles bleus pâles) et des quadruples de points (tétraèdres bleu foncé).

Complexe de Vietoris–Rips

En topologie, le complexe de Vietoris–Rips, également appelé complexe de Vietoris ou complexe de Rips, est une manière de former un espace topologique à partir des distances dans un ensemble de points. Il s'agit d'un complexe simplicial abstrait qui peut être défini à partir de tout espace métrique M et d'une distance δ, en formant un simplexe pour chaque ensemble fini de points ayant un diamètre au plus égal à δ. Autrement dit, il s'agit d'une famille de sous-ensembles finis de M, où l'on considère qu'un sous-ensemble de k points forme un simplexe de dimension k - 1 (une arête pour deux points, un triangle pour trois points, un tétraèdre pour quatre points, etc.) ; si un ensemble fini S a la propriété que la distance entre chaque paire de points de S est au plus égale à δ, alors S est inclus en tant que simplexe dans le complexe.

Histoire

Le complexe de Vietoris–Rips a été initialement appelé complexe de Vietoris, en l'honneur de Leopold Vietoris, qui l'a introduit comme un moyen d'étendre la théorie de l'homologie des complexes simpliciaux aux espaces métriques. Après qu'Eliyahu Rips a appliqué le même complexe à l'étude des groupes hyperboliques, son utilisation a été popularisée par Mikhail Gromov (1987), qui l'a appelé le complexe de Rips. Le nom complexe de Vietoris–Rips est dû à Jean-Claude Hausmann (1995).

Relation avec le complexe de Čech

Le complexe de Vietoris–Rips est étroitement lié au complexe de Čech (ou nerf) d'un ensemble de boules, qui possède un simplexe pour chaque sous-ensemble fini de boules ayant une intersection non vide. Dans un espace géodésiquement convexe Y, le complexe de Vietoris–Rips de tout sous-espace X ⊂ Y pour une distance δ possède les mêmes points et arêtes que le complexe de Čech de l'ensemble des boules de rayon δ/2 dans Y centrées aux points de X. Cependant, contrairement au complexe de Čech, le complexe de Vietoris–Rips de X dépend uniquement de la géométrie intrinsèque de X, et non d'un éventuel plongement de X dans un espace plus grand.

Par exemple, considérons l'espace métrique uniforme M₃ composé de trois points, chacun à une distance unitaire des autres. Le complexe de Vietoris–Rips de M₃, pour δ = 1, inclut un simplexe pour chaque sous-ensemble de points de M₃, incluant un triangle pour M₃ lui-même. Si nous plongeons M₃ sous forme d'un triangle équilatéral dans le plan euclidien, le complexe de Čech des boules de rayon 1/2 centrées aux points de M₃ contiendrait tous les autres simplexes du complexe de Vietoris–Rips mais ne contiendrait pas ce triangle, car il n'existe aucun point du plan contenu dans les trois boules. Cependant, si M₃ est plongé dans un espace métrique contenant un quatrième point à une distance de 1/2 de chacun des trois points de M₃, le complexe de Čech des boules de rayon 1/2 dans cet espace contiendrait le triangle. Ainsi, le complexe de Čech des boules de rayon fixe centrées à M₃ diffère selon l'espace plus grand dans lequel M₃ peut être plongé, tandis que le complexe de Vietoris–Rips reste inchangé.

Si un espace métrique X est plongé dans un espace métrique injectif Y, le complexe de Vietoris–Rips pour une distance δ et X coïncide avec le complexe de Čech des boules de rayon δ/2 centrées aux points de X dans Y. Ainsi, le complexe de Vietoris–Rips de tout espace métrique M est égal au complexe de Čech d'un système de boules dans l'enveloppe serrée de M.

Relation avec les graphes à disque unité et les complexes de cliques

Le complexe de Vietoris–Rips pour δ = 1 contient une arête pour chaque paire de points qui sont à une distance unitaire ou moins dans l'espace métrique donné. Ainsi, son 1-squelette est le graphe à disque unité de ses points. Il contient un simplexe pour chaque clique dans le graphe à disque unité, de sorte qu'il est le complexe de clique ou complexe drapeau du graphe à disque unité. Plus généralement, le complexe de clique de tout graphe G est un complexe de Vietoris–Rips pour l'espace métrique ayant pour points les sommets de G et pour distances les longueurs des chemins les plus courts dans G.

Autres résultats

Si M est une variété riemannienne fermée, alors pour des valeurs suffisamment petites de δ, le complexe de Vietoris–Rips de M, ou des espaces suffisamment proches de M, est homotope à M lui-même.

Chambers, Erickson & Worah (2008) ont décrit des algorithmes efficaces pour déterminer si un cycle donné est contractible dans le complexe de Rips de tout ensemble fini de points dans le plan euclidien.

Applications

Comme pour les graphes à disque unité, le complexe de Vietoris–Rips a été appliqué en informatique pour modéliser la topologie des réseaux de communication sans fil ad hoc. Un avantage du complexe de Vietoris–Rips dans cette application est qu'il peut être déterminé uniquement à partir des distances entre les nœuds de communication, sans avoir à déduire leur position physique exacte. Un inconvénient est que, contrairement au complexe de Čech, le complexe de Vietoris–Rips ne fournit pas directement d'informations sur les lacunes de couverture de communication, mais ce défaut peut être atténué en sandwichant le complexe de Čech entre deux complexes de Vietoris–Rips pour différentes valeurs de δ. Une implémentation des complexes de Vietoris–Rips est disponible dans le package R TDAstats.

Les complexes de Vietoris–Rips ont également été appliqués à l'extraction de caractéristiques dans les données d'images numériques ; dans cette application, le complexe est construit à partir d'un espace métrique de haute dimension dans lequel les points représentent des caractéristiques d'image de bas niveau.

La collection de tous les complexes de Vietoris–Rips est une construction couramment utilisée en homologie persistante et en analyse topologique des données, et est connue sous le nom de filtration de Rips.

Références

• Carlsson, 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, 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