Комплекс Вьеториса — Рипса

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Комплекс Вьеториса — Рипса множества из 23 точек на евклидовой плоскости. Этот комплекс имеет множества размером от одной до четырёх точек — сами точки (показаны красными кружочками), пары точек (чёрные рёбра), тройки точек (светло-синие треугольники) и четвёрки точек (тёмно-синие тетраэдры).

Комплекс Вьеториса — Рипса, называемый также комплексом Вьеториса или Комплексом Рипса − способ образования топологического пространства из расстояний в множестве точек. Это абстрактный симплициальный комплекс[англ.], который может быть определён из любого метрического пространства M и расстояния путём образования симплекса для любого конечного множества точек, имеющего диаметр, не превосходящий . То есть это семейство конечных подмножеств метрического пространства M, под которым понимается подмножество из k точек как (k−1)-мерный симплекс (ребро для двух точек, треугольник для трёх, тетраэдр для четырёх и т.д.). Если же конечное множество S обладает свойством, при котором расстояние между любой парой точек в S не превосходит , то S включается в качестве симплекса в комплекс.

Комплекс Вьеториса — Рипса первоначально назывался комплексом Вьеториса в честь Леопольда Вьеториса, который ввёл его как средство расширения теории гомологий из симплициальных комплексов метрических пространств[1][2][3][4]. После того, как Илья Аронович Рипс употребил некоторые комплексы для изучения гиперболических групп, их применения популяризировал Михаил Леонидович Громов[5], который назвал их комплексами Рипса[3][4]. Название «Комплекс Вьеториса — Рипса» принадлежит Хаусману[3][4].

Связь с комплексами Чеха

[править | править код]

Комплекс Вьеториса — Рипса тесно связан с комплексом Чеха (или нервом) множества шаров, который имеет симплекс для любого конечного подмножества шаров с ненулевым пересечением. В геодезически выпуклом пространстве[англ.] Y комплекс Вьеториса — Рипса любого подпространства для расстояния имеет те же самые точки и рёбра, что и комплекс Чеха множества шаров радиуса в Y, имеющих центры в точках множества X. Однако, в отличие от комплекса Чеха, комплекс Вьеториса — Рипса для X зависит только от внутренней геометрии X, а не от какого-либо вложения X в некоторое большее пространство.

Как пример, рассмотрим однородное метрическое пространство M3, состоящее из трёх точек, каждая из которых находится на расстоянии единицы от других. Комплекс Вьеториса — Рипса для M3 для включает симплекс для любого подмножества точек из M3, включая сам треугольник M3. Если мы вложим M3 как правильный треугольник в евклидову плоскость, то комплекс Чеха шаров радиуса 1/2 с центрами в точках M3 будет содержать все остальные симплексы комплекса Вьеториса — Рипса, но не будет содержать треугольник, поскольку нет точки на плоскости, принадлежащей всем трём шарам. Однако, если M3 вместо этого вложено в метрическое пространство, которое содержит четвёртую точку на расстоянии 1/2 от каждой точки M3, комплекс Чеха для шаров радиуса 1/2 в этом пространстве будет содержать треугольник. Таким образом, комплекс Чеха для фиксированного радиуса шаров с центрами M3 зависит от пространства, в которое M3 может быть вложено, в то время как комплекс Вьеториса — Рипса остаётся неизменным

Если метрическое пространство X вложено в инъективное метрическое пространство Y, Комплекс Вьеториса — Рипса для расстояния и множества X совпадает с комплексом Чеха шаров радиуса , имеющих центры в точках X в Y. Таким образом, комплекс Вьеториса — Рипса любого метрического пространства M равен комплексу Чеха системы шаров в инъективной оболочке пространства M.

Связь с графами единичных кругов и кликовыми комплексами

[править | править код]

Комплекс Вьеториса — Рипса для содержит ребро для любой пары точек, которые находятся на единичном или менее расстоянии в заданном метрическом пространстве. А тогда его 1-скелет[англ.] — это граф единичных кругов его точек. Он содержит симплекс для любой клики в графе единичных кругов, так что он является флаговым комплексом (или кликовым комплексом) графа единичных кругов[6]. Более обще, кликовый комплекс любого графа G является комплексом Вьеториса — Рипса для метрического пространства, имеющего в качестве точек вершины графа G и имеющего в качестве расстояния длины кратчайших путей в G.

Другие результаты

[править | править код]

Если M — замкнутое риманово многообразие, то для достаточно малых значений комплекс Вьеториса — Рипса для M или пространства, достаточно близкие к M, гомотопически эквивалентны самому M[3][7].

Чамберс, Эриксон и Вора[6] описали эффективные алгоритмы определения, стягивается ли данный цикл в комплексе Рипса любого конечного множества на евклидовой плоскости.

Приложения

[править | править код]

Как и в случае единичных дисковых графов, комплекс Вьеториса — Рипса применяется в информатике для моделирования топологии беспроводных ad-hoc-сетей. Одним из преимуществ комплекса Вьеториса — Рипса в этом приложении является то, что он может быть задан исходя лишь из расстояний между взаимодействующими узлами без необходимости знания их физического местоположения. Недостатком является то, что в отличие от комплекса Чеха, комплекс Вьеториса — Рипса не обеспечивает непосредственно информацию о дырах в коммуникационном покрытии, но этот недостаток можно уменьшить путём размещения комплекса Чеха между двумя комплексами Вьеториса — Рипса для различных значений [8][9]. Имплементацию комплексов Вьеториса — Рипса можно найти в R пакете TDAstats[10].

Комплексы Вьеториса — Рипса применяются также для выделения признаков в изображениях. В этом приложении комплекс строится в метрическом пространстве высокой размерности, в котором точки представляют признаки изображения низкого порядка [11].

Примечания

[править | править код]

Литература

[править | править код]
  • Erik Carlsson, Gunnar Carlsson, Vin de Silva. An algebraic topological method for feature identification // International Journal of Computational Geometry and Applications. — 2006. — Т. 16, вып. 4. — С. 291–314. — doi:10.1142/S021819590600204X.
  • Erin W. Chambers, Jeff Erickson, Pratik Worah. Testing contractibility in planar Rips complexes // Proceedings of the 24th Annual ACM Symposium on Computational Geometry. — 2008. — С. 251–259. — doi:10.1145/1377676.1377721.
  • Frédéric Chazal, Steve Oudot. Towards Persistence-Based Reconstruction in Euclidean Spaces // ACM Symposium on Computational Geometry. — 2008. — С. 232–241. — ISBN 978-1-60558-071-5. — doi:10.1145/1377676.1377719. — arXiv:0712.2638.
  • Vin de Silva, Robert Ghrist. Coordinate-free coverage in sensor networks with controlled boundaries via homology // The International Journal of Robotics Research. — 2006. — Т. 25. — С. 1205–1222. — doi:10.1177/0278364906072252.
  • Mikhail Leonidovich Gromov. Hyperbolic groups // Essays in group theory. — Springer-Verlag, 1987. — Т. 8. — С. 75–263. — (Mathematical Sciences Research Institute Publications).
  • Jean-Claude Hausmann. On the Vietoris–Rips complexes and a cohomology theory for metric spaces // Prospects in Topology: Proceedings of a conference in honour of William Browder. — Princeton University Press, 1995. — Т. 138. — С. 175–188. — (Annals of Mathematics Studies)..
  • Janko Latschev. Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold // Archiv der Mathematik. — 2001. — Т. 77, вып. 6. — С. 522–528. — doi:10.1007/PL00000526.
  • Solomon Lefschetz. Algebraic Topology. — New York: Amer. Math. Soc., 1942. — С. 271.
  • Muhammad A., Jadbabaie A. Dynamic coverage verification in mobile sensor networks via switched higher order Laplacians // Robotics: Science and Systems / editor: Oliver Broch. — MIT Press, 2007.
  • Heinrich Reitberger. Leopold Vietoris (1891–2002) // Notices of the American Mathematical Society. — 2002. — Т. 49, вып. 20.
  • Leopold Vietoris. Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen // Mathematische Annalen. — 1927. — Т. 97, вып. 1. — С. 454–472. — doi:10.1007/BF01447877.
  • Raoul Wadhwa, Drew Williamson, Andrew Dhawan, Jacob Scott. TDAstats: R pipeline for computing persistent homology in topological data analysis // Journal of Open Source Software. — 2018. — Т. 3, вып. 28. — С. 860. — doi:10.21105/joss.00860.