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

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

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

История

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

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

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

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

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

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

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

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

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

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

Приложения

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

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