Комплекс Виеторис-Рипс

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

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

История

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

Отношение к чешскому комплексу

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

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

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

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

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

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

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

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

Приложения

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

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

Сбор всех комплексов Вьеториса-Рипса является широко применяемой конструкцией в анализе устойчивой гомологии и топологических данных и известен как фильтрация Рипса .

Ссылки

• Карлссон, Эрик; Карлссон, Гуннар ; де Сильва, Вин (2006), «Алгебраический топологический метод идентификации объектов» (PDF) , Международный журнал вычислительной геометрии и приложений , 16 (4): 291–314, doi : 10.1142/S021819590600204X , S2CID   5831809 , заархивировано из оригинал (PDF) от 04 марта 2019 г.
• Чемберс, Эрин В.; Эриксон, Джефф; Вора, Пратик (2008), «Тестирование сжимаемости в плоских комплексах Rips» , Труды 24-го ежегодного симпозиума ACM по вычислительной геометрии стр. 251–259, CiteSeerX   10.1.1.296.6424 , doi : 10.1145/1377676.1377721 , 8072058   , .
• Шазаль, Фредерик; Удо, Стив (2008), «К реконструкции на основе постоянства в евклидовых пространствах», Труды двадцать четвертого ежегодного симпозиума по вычислительной геометрии , стр. 232–241, arXiv : 0712.2638 , doi : 10.1145/1377676.1377719 , ISBN  978-1-60558-071-5 , S2CID   1020710 {{citation}}: CS1 maint: дата и год ( ссылка ) .
• де Сильва, Вин; Грист, Роберт (2006), «Безкоординатное покрытие в сенсорных сетях с контролируемыми границами посредством гомологии», The International Journal of Robotics Research , 25 (12): 1205–1222, doi : 10.1177/0278364906072252 , S2CID   10210836 .
• Громов, Михаил (1987), «Гиперболические группы», Очерки теории групп , НИИ математических наук Публикации , вып. 8, Springer-Verlag, стр. 75–263 .
• Хаусманн, Жан-Клод (1995), «О комплексах Виеториса – Рипса и теории когомологий для метрических пространств», Перспективы топологии: материалы конференции в честь Уильяма Браудера , Анналы математических исследований, том. 138, Princeton University Press , стр. 175–188, MR   1368659 .
• Лачев, Янко (2001), «Комплексы Вьеториса–Рипса метрических пространств вблизи замкнутого риманова многообразия», Archiv der Mathematik , 77 (6): 522–528, doi : 10.1007/PL00000526 , MR   1879057 , S2CID   119878137 .
• Лефшец, Соломон (1942), Алгебраическая топология , Нью-Йорк: Амер. Математика. Соц., с. 271, МР   0007093 .
• Мухаммед, А.; Джадбабаи, А. (2007), «Динамическая проверка покрытия в мобильных сенсорных сетях с помощью коммутируемых лапласианов высшего порядка» (PDF) , в Брох, Оливер (ред.), Робототехника: наука и системы , MIT Press .
• Райтбергер, Генрих (2002), «Леопольд Вьеторис (1891–2002)» (PDF) , Уведомления Американского математического общества , 49 (20) .
• Виеторис, Леопольд (1927), «О высшей связности компактов и классе непротиворечивых отображений», Mathematical Annals , 97 (1): 454–472, doi : 10.1007/BF01447877 , S2CID   121172198 .
• Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (2018), «TDAstats: конвейер R для вычисления постоянной гомологии при анализе топологических данных», Journal of Open Source Software , 3 (28): 860, Bibcode : 2018JOSS....3..860R , doi : 10.21105 /joss.00860 , PMC   7771879 , PMID   33381678