В топологии комплекс Виеториса –Рипса , также называемый комплексом Виеториса или комплексом Рипса , является способом формирования топологического пространства из расстояний в наборе точек. Это абстрактный симплициальный комплекс , который может быть определен из любого метрического пространства 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]
{{citation}}: CS1 maint: дата и год ( ссылка ).