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

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

История

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

Примечания

  1. ^ Виеторис (1927); Лефшец (1942); Хаусманн (1995); Райтбергер (2002).
  2. ^ Хаусманн (1995); Райтбергер (2002).
  3. ^ Райтбергер (2002).
  4. ^ Чемберс, Эриксон и Вора (2008).
  5. ^ Хаусманн (1995), Лачев (2001).
  6. ^ де Сильва и Христо (2006), Мухаммад и Джадбабайе (2007).
  7. ^ Вадхва и др. 2018.
  8. ^ Карлссон, Карлссон и де Сильва (2006).
  9. ^ Дей, Тамал К.; Ши, Даю; Ван, Юсу (2019-01-30). «SimBa: эффективный инструмент для аппроксимации устойчивости фильтрации Rips с помощью симплициального пакетного коллапса». ACM Journal of Experimental Algorithmics . 24 : 1.5:1–1.5:16. doi : 10.1145/3284360 . ISSN  1084-6654. S2CID  216028146.

Ссылки

  • Карлссон, Эрик; Карлссон, Гуннар ; де Сильва, Вин (2006), «Алгебраический топологический метод идентификации признаков» (PDF) , International Journal of Computational Geometry and Applications , 16 (4): 291–314, doi :10.1142/S021819590600204X, S2CID  5831809, архивировано из оригинала (PDF) 2019-03-04.
  • Chambers, Erin W .; Erickson, Jeff; Worah, Pratik (2008), «Тестирование сжимаемости в плоских комплексах Rips», Труды 24-го ежегодного симпозиума ACM по вычислительной геометрии , стр. 251–259, CiteSeerX  10.1.1.296.6424 , doi :10.1145/1377676.1377721, S2CID  8072058.
  • Шазаль, Фредерик; Удо, Стив (2008), «К реконструкции на основе сохранения в евклидовых пространствах», Труды двадцать четвертого ежегодного симпозиума по вычислительной геометрии , стр. 232–241, arXiv : 0712.2638 , doi : 10.1145/1377676.1377719, ISBN 978-1-60558-071-5, S2CID  1020710{{citation}}: CS1 maint: дата и год ( ссылка ).
  • де Сильва, Вин; Грист, Роберт (2006), «Безкоординатное покрытие в сенсорных сетях с контролируемыми границами посредством гомологии», Международный журнал исследований робототехники , 25 (12): 1205–1222, doi :10.1177/0278364906072252, S2CID  10210836.
  • Громов, Михаил (1987), «Гиперболические группы», Очерки по теории групп , Издательства НИИ математических наук , т. 8, Springer-Verlag, стр. 75–263.
  • Хаусманн, Жан-Клод (1995), «О комплексах Виеториса–Рипса и теории когомологий для метрических пространств», Перспективы в топологии: Труды конференции в честь Уильяма Браудера , Annals of Mathematics Studies, т. 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), Алгебраическая топология , Нью-Йорк: Amer. Math. Soc., стр. 271, MR  0007093.
  • Мухаммад, А.; Джадбабаи, А. (2007), «Динамическая проверка покрытия в мобильных сенсорных сетях с помощью переключаемых лапласианов высшего порядка» (PDF) , в Broch, Oliver (ред.), Robotics: Science and Systems , MIT Press.
  • Рейтбергер, Генрих (2002), «Леопольд Виеторис (1891–2002)» (PDF) , Notices of the American Mathematical Society , 49 (20).
  • Виеторис, Леопольд (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.
  • Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (2018), «TDAstats: конвейер R для вычисления постоянной гомологии в топологическом анализе данных», Журнал программного обеспечения с открытым исходным кодом , 3 (28): 860, Bibcode : 2018JOSS....3..860R, doi : 10.21105/joss.00860 , PMC  7771879 , PMID  33381678
Взято с "https://en.wikipedia.org/w/index.php?title=Vietoris–Rips_complex&oldid=1251187205"