Комплекс Виеторис – Рипс - Vietoris–Rips complex

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

В топология, то Комплекс Виеторис – Рипс, также называемый Комплекс Виеторис или Рипс сложный, является абстрактный симплициальный комплекс что может быть определено из любого метрическое пространство M и расстояние δ, образуя симплекс для каждого конечный набор точек, которые имеют диаметр не более δ. То есть это семейство конечных подмножеств M, в котором мы думаем о подмножестве k точки как образующие (k - 1) -мерный симплекс (ребро для двух точек, треугольник для трех точек, тетраэдр для четырех точек и т. Д.); если конечное множество S обладает тем свойством, что расстояние между каждой парой точек в S не превосходит δ, то включаем S как симплекс в комплексе.

История

Комплекс Виеторис – Рипс первоначально назывался комплексом Виеторис, так как Леопольд Виеторис, который ввел его как средство расширения теория гомологии от симплициальных комплексов к метрическим пространствам.[1] После Элияху Рипс применил тот же комплекс к изучению гиперболические группы, его использование было популяризировано Михаил Громов  (1987 ), который назвал это комплексом Рипса.[2] Название «Комплекс Виеторис – Рипс» связано с Жан-Клод Хаусманн  (1995 ).[3]

Отношение к комплексу Чеха

Комплекс Виеториса – Рипса тесно связан с Чешский комплекс (или нерв ) набора мячи, который имеет симплекс для каждого конечного подмножества шаров с непустым пересечением: в геодезически выпуклое пространство Y, комплекс Виеториса – Рипса любого подпространства Икс ⊂ Y для расстояния δ имеет те же точки и ребра, что и комплекс Чеха множества шаров радиуса δ / 2 в Y которые сосредоточены в точках Икс. Однако, в отличие от комплекса Чеха, комплекс Виеториса – Рипса Икс зависит только от внутренней геометрии Икс, а не при внедрении Икс в какое-то большее пространство.

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

Если метрическое пространство Икс встроен в инъективное метрическое пространство Yкомплекс Виеториса – Рипса для расстояния δ и Икс совпадает с комплексом Чеха шаров радиуса δ / 2 с центрами в точках Икс в Y. Таким образом, комплекс Виеториса – Рипса любого метрического пространства M равен комплексу Чеха системы шаров в тесный промежуток из M.

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

Комплекс Вьеториса – Рипса для δ = 1 содержит ребро для каждой пары точек, находящихся на единичном расстоянии или меньше в данном метрическом пространстве. Таким образом, его 1-скелет это граф единичного диска своих точек. Он содержит симплекс для каждого клика в графе единичного диска, так что это кликовый комплекс или флаговый комплекс графа единичного диска.[4] В более общем смысле, кликовый комплекс любого графа г является комплексом Виеториса – Рипса для метрического пространства, имеющего в качестве точек вершины из г и имея в качестве расстояний длины кратчайшие пути в г.

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

Если M закрытый Риманово многообразие, то при достаточно малых значениях δ комплекс Виеториса – Рипса M, или пространств, достаточно близких к M, является гомотопический эквивалент к M сам.[5]

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

Приложения

Как и в случае графов единичного диска, комплекс Виеториса – Рипса применялся в Информатика моделировать топологию специальные сети беспроводной связи. Одним из преимуществ комплекса Вьеториса – Рипса в этом приложении является то, что его можно определить только по расстояниям между узлами связи, без необходимости делать выводы об их точном физическом расположении. Недостатком является то, что, в отличие от комплекса Чеха, комплекс Виеториса – Рипса не предоставляет напрямую информацию о пробелах в коммуникационном покрытии, но этот недостаток может быть исправлен путем размещения комплекса Чеха между двумя комплексами Виеториса – Рипса для разных значений δ.[6] Полезную реализацию комплексов Вьеторис-Рипс можно найти в TDAstats Пакет R.[7]

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

Заметки

  1. ^ Вьеторис (1927); Лефшец (1942); Хаусманн (1995); Рейтбергер (2002).
  2. ^ Хаусманн (1995); Рейтбергер (2002).
  3. ^ Рейтбергер (2002).
  4. ^ Чемберс, Эриксон и Вора (2008).
  5. ^ Хаусманн (1995), Лачев (2001).
  6. ^ де Сильва и Грист (2006), Мухаммад и Джадбабайе (2007).
  7. ^ Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (2018). «TDAstats: конвейер R для вычисления устойчивой гомологии при анализе топологических данных». Журнал открытого программного обеспечения. 3 (28): 860. Дои:10.21105 / joss.00860.
  8. ^ Карлссон, Карлссон и де Сильва (2006).

использованная литература