Симплексное дерево

Пример симплициального комплекса и соответствующая структура данных симплексного дерева. Обратите внимание, что два нижних узла имеют путь к узлу, равный 4, что указывает на два трехмерных симплекса, состоящих из четырех вершин каждый.

В топологическом анализе данных симплексное дерево — это тип дерева, используемого для эффективного представления любого общего симплициального комплекса . Через свои узлы эта структура данных явно представляет все симплексы. Его гибкая структура позволяет реализовать множество основных операций, полезных для вычисления устойчивой гомологии . Эта структура данных была изобретена Жаном-Даниэлем Буассонна и Клеманом Марией в 2014 году в статье Симплексное дерево: эффективная структура данных для общих симплициальных комплексов . Эта структура данных предлагает эффективные операции с разреженными симплициальными комплексами. Для плотных или максимальных симплексов Skeleton-Blocker представления или карта топлекса используются представления.

Определения

Многие исследователи топологического анализа данных считают симплексное дерево наиболее компактной структурой данных на основе симплекса для симплициальных комплексов и структурой данных, позволяющей интуитивное понимание симплициальных комплексов благодаря комплексному использованию их математических свойств.

Эвристическое определение

Рассмотрим любой симплициальный комплекс — это набор , состоящий из точек (0 измерений), отрезков прямых (1 измерение), треугольников (2 измерения) и их n -мерных аналогов , называемых n- симплексами в топологическом пространстве. По математическим свойствам симплексов любой n- симплекс состоит из кратных $(n-1)$- симплексы . Таким образом, линии состоят из точек, треугольники из линий, тетраэдры из треугольников. Обратите внимание, что каждый более высокий уровень добавляет 1 вершину к вершинам n- симплекса . Структура данных основана на симплексе, поэтому она должна однозначно представлять все симплексы по точкам, определяющим симплекс. Простой способ добиться этого — определить каждый симплекс по его точкам в отсортированном порядке.

Позволять $\mathrm {K}$ — симплициальный комплекс размерности k, $V$ его множество вершин, где вершины помечены от 1 до $\left\vert V\right\vert$ и заказал соответственно. Теперь создайте размер словаря $\left\vert V\right\vert$ содержащий все метки вершин по порядку. Это представляет собой 0-мерные симплексы. Затем для пути к начальному словарю каждой записи в исходном словаре добавьте в качестве дочернего словаря все вершины, полностью связанные с текущим набором вершин, каждая из которых имеет метку больше, чем $l$. Представьте этот шаг на k уровнях. Очевидно, что если первый словарь имеет глубину 0, то любая запись на глубине $\tau$ любого словаря в этой структуре данных однозначно представляет собой $\tau$-симплекс внутри $\mathrm {K}$. Для полноты точки зрения исходный словарь считается представлением пустого симплекса. Для практичности операций метки, повторяющиеся на одном уровне, связываются вместе, образуя зацикленный связанный список. Наконец, дочерние словари также имеют указатели на родительский словарь для быстрого доступа к предку.

Конструктивное определение

Позволять $\mathrm {K}$ — симплициальный комплекс размерности k. Начнем с разложения симплициального комплекса на взаимоисключающие симплексы. Этого можно достичь жадным способом, итеративно удаляя из симплициального комплекса симплексы высшего порядка до тех пор, пока симплициальный комплекс не станет пустым. Затем нам нужно пометить каждую вершину от 1 до $\left\vert V\right\vert$ и свяжем каждый симплекс с соответствующим ему «словом», то есть упорядоченным списком его вершин по меткам. Порядок меток гарантирует отсутствие повторений в симплексном дереве, поскольку существует только один способ описания симплекса. Мы начинаем с нулевого корня, представляющего нулевой симплекс. Затем мы перебираем все симплексы и каждую метку каждого симплексного слова. Если метка доступна как дочерний элемент текущего корня, сделайте этот дочерний элемент временным корнем процесса вставки, в противном случае создайте новый узел для дочернего элемента, сделайте его новым временным корнем и продолжите работу с остальной частью слова. В ходе этого процесса k словарей поддерживаются со всеми метками и вставляют адрес узла для соответствующей метки. Если адрес уже находится в этом месте словаря, создается указатель от старого узла к новому узлу. После завершения процесса все дочерние элементы каждого узла вводятся в словарь, и все указатели зацикливаются для создания зацикленных связанных списков. Здесь может быть применен широкий спектр словарей, таких как хеш-таблицы, но некоторые операции предполагают возможность упорядоченного обхода записей, что приводит к тому, что большинство реализаций, использующих красно-черные деревья, являются словарями.

Операции

Хотя симплексные деревья не являются наиболее эффективными структурами данных для симплициального комплексного представления, их операции с разреженными данными считаются современными. Здесь мы даем границы различных полезных операций, возможных с помощью этого представления. Доступно множество реализаций этих операций.

Сначала введем обозначения. Учитывать $s$ заданный симплекс, $\sigma$ заданный узел, соответствующий последней вершине $s$, $l$ — метка, связанная с этим узлом, $j$ - глубина этого узла, $k$ - размерность симплициального комплекса, $D_{\sigma }$ — максимальное количество операций для доступа $\sigma$ в словаре (если словарь представляет собой красно-черное дерево, $D_{\sigma }=O(log(deg(\sigma )))$ это сложность). Учитывать $C_{s}$ количество софасов $s$, и $N_{l}^{>j}$ — количество узлов симплексного дерева, заканчивающихся меткой $l$ на глубине больше, чем $j$. Уведомление $N_{l}^{>j}\leq C_{s}$.

1. Поиск , вставка и удаление слов выполняются в $O(jD_{\sigma })$.
2. Вставка и удаление всего симплекса выполняется в $O(2^{j}D_{\sigma })$.
3. Вычисление устойчивой гомологии или, более сложным способом, вычисление чисел Бетти с наиболее эффективным использованием симплексного дерева остается открытой проблемой, однако текущие алгоритмы для этой задачи на разреженных симплициальных комплексах достигают современной производительности.
4. Структура симплексных деревьев допускает элементарное схлопывание раскладных симплексов, однако границы этой операции в общем случае неизвестны.
5. Подслучай элементарного коллапса — это сжатие ребер . Краевое сжатие может быть

достигнуто в $O(kN_{l}^{>j}+C_{s}D_{\sigma })$.

1. Нахождение кограней данного симплекса может быть достигнуто в $O(kN_{l}^{>j})$.
2. Нахождение сограней данного симплекса может быть достигнуто в $O(j^{2}D_{\sigma })$.

Что касается конструкции, то, как видно из конструктивного определения, конструкция пропорциональна числу и сложности симплексов в симплициальном комплексе. Это может быть особенно дорого, если симплициальный комплекс плотный. Тем не менее, некоторые оптимизации для конкретных симплициальных комплексов, в том числе для комплексов Флага , комплексов Рипса и комплексов Свидетелей .

Приложения

Симплексные деревья эффективны в разреженных симплициальных комплексах. Для этой цели многие алгоритмы постоянной гомологии, ориентированные на многомерные реальные данные (часто разреженные), используют в этих алгоритмах симплексные деревья. Хотя симплексные деревья не так эффективны, как матрица инцидентности, их симплексная структура позволяет им эффективно использоваться для хранения симплексных комплексов в алгоритмах постоянной гомологии.