árbol simplex

Datos topológicos

Un ejemplo de complejo simplicial y la correspondiente estructura de datos de árbol simplex. Observe que los dos nodos más bajos tienen una ruta de 4 hacia el nodo, lo que indica los 2 símplex tridimensionales compuestos de 4 vértices cada uno.

En el análisis de datos topológicos , un árbol simplex es un tipo de trie utilizado para representar eficientemente cualquier complejo simplicial general . A través de sus nodos, esta estructura de datos representa explícitamente todos los simples. Su estructura flexible permite la implementación de muchas operaciones básicas útiles para calcular la homología persistente . Esta estructura de datos fue inventada por Jean-Daniel Boissonnat y Clément Maria en 2014, en el artículo The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes . ^[1] Esta estructura de datos ofrece operaciones eficientes en complejos simpliciales dispersos. Para simplices densos o máximos, se utilizan representaciones Skeleton-Blocker ^[2] o representaciones Toplex Map ^{[3] .}

Definiciones

Muchos investigadores en análisis de datos topológicos consideran que el árbol simplex es la estructura de datos simplex más compacta para complejos simpliciales, y una estructura de datos que permite una comprensión intuitiva de los complejos simpliciales debido al uso integrado de sus propiedades matemáticas. ^{[1] [3] [4]}

Definición heurística

Considere que cualquier complejo simplicial es un conjunto compuesto por puntos (0 dimensiones), segmentos de línea (1 dimensión), triángulos (2 dimensiones) y sus contrapartes n -dimensionales , llamadas n- simplex dentro de un espacio topológico. Según las propiedades matemáticas de los símplex, cualquier n- símplex está compuesto de múltiples símplex . Así, las rectas se componen de puntos, los triángulos de rectas, los tetraedros de triángulo. Observe que cada nivel superior agrega 1 vértice a los vértices del n- simplex . La estructura de datos está basada en símplex, por lo tanto, debe representar todos los símplex de forma única mediante los puntos que definen el símplex. Una forma sencilla de lograr esto es definir cada simplex por sus puntos en orden. ${\displaystyle (n-1)}$

Sea un complejo simplicial de dimensión k, su conjunto de vértices, donde los vértices están etiquetados del 1 al y ordenados en consecuencia. Ahora, construya un tamaño de diccionario que contenga todas las etiquetas de vértices en orden. Esto representa los símplex de dimensión 0. Luego, para la ruta al diccionario inicial de cada entrada en el diccionario inicial, agregue como diccionario secundario todos los vértices completamente conectados al conjunto actual de vértices, todos los cuales tengan una etiqueta mayor que . Representa este paso en k niveles. Claramente, considerando el primer diccionario como profundidad 0, cualquier entrada en profundidad de cualquier diccionario en esta estructura de datos representa de forma única un -simplex dentro de . Para completar, el punto al diccionario inicial se considera la representación del simplex vacío. Para que las operaciones sean prácticas, las etiquetas que se repiten en el mismo nivel se vinculan entre sí, formando una lista vinculada en bucle. Finalmente, los diccionarios secundarios también tienen punteros a su diccionario principal, para un acceso rápido a los antepasados. ^[1] ${\displaystyle \mathrm {K} }$ ${\displaystyle V}$ ${\displaystyle \left\vert V\right\vert }$ ${\displaystyle \left\vert V\right\vert }$ ${\displaystyle l}$ ${\displaystyle \tau }$ ${\displaystyle \tau }$ ${\displaystyle \mathrm {K} }$

Definición constructiva

Sea un complejo simple de dimensión k. Comenzamos descomponiendo el complejo simplicial en simples mutuamente excluyentes. Esto se puede lograr de manera codiciosa eliminando iterativamente del complejo simplicial los símplex de orden más alto hasta que el complejo simplicial esté vacío. Luego necesitamos etiquetar cada vértice de 1 a y asociar cada simplex con su "palabra" correspondiente, es decir, la lista ordenada de sus vértices por etiqueta. Ordenar las etiquetas garantiza que no haya repeticiones en el árbol simplex, ya que solo hay una forma de describir un árbol simplex. Comenzamos con una raíz nula, que representa el simplex nulo. Luego, iteramos a través de todos los simples y a través de cada etiqueta de cada palabra simple. Si la etiqueta está disponible como hijo de la raíz actual, convierta a ese hijo en la raíz temporal del proceso de inserción; de lo contrario, cree un nuevo nodo para el hijo, conviértalo en la nueva raíz temporal y continúe con el resto de la palabra. Durante este proceso se mantienen k diccionarios con todas las etiquetas y se inserta la dirección del nodo para la etiqueta correspondiente. Si ya hay una dirección en ese espacio en el diccionario, se crea un puntero desde el nodo antiguo al nuevo nodo. Una vez finalizado el proceso, todos los elementos secundarios de cada nodo se ingresan en un diccionario y todos los punteros se repiten para crear listas enlazadas en bucle. Aquí se podría aplicar una amplia gama de diccionarios, como tablas hash, pero algunas operaciones asumen la posibilidad de un recorrido ordenado de las entradas, lo que lleva a que la mayoría de las implementaciones utilicen árboles rojo-negro como diccionarios. ^[1] ${\displaystyle \mathrm {K} }$ ${\displaystyle \left\vert V\right\vert }$

Operaciones

Si bien los árboles simplex no son las estructuras de datos más eficientes en cuanto a espacio para una representación compleja simple, sus operaciones con datos dispersos se consideran de última generación. Aquí, damos los límites de diferentes operaciones útiles posibles a través de esta representación. Muchas implementaciones de estas operaciones están disponibles. ^{[1] [4] [5] [6] [7]}

Primero introducimos la notación. Considere es un simplex dado, es un nodo dado correspondiente al último vértice de , es la etiqueta asociada a ese nodo, es la profundidad de ese nodo, es la dimensión del complejo simplicial, es el número máximo de operaciones a las que acceder en un diccionario (si el diccionario es un árbol rojo-negro, es la complejidad). Considere el número de cocaras de y el número de nodos del árbol simplex que termina con la etiqueta a una profundidad mayor que . Aviso . ${\displaystyle s}$ ${\displaystyle \sigma }$ ${\displaystyle s}$ ${\displaystyle l}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle D_{\sigma }}$ ${\displaystyle \sigma }$ ${\displaystyle D_{\sigma }=O(log(deg(\sigma )))}$ ${\displaystyle C_{s}}$ ${\displaystyle s}$ ${\displaystyle N_{l}^{>j}}$ ${\displaystyle l}$ ${\displaystyle j}$ ${\displaystyle N_{l}^{>j}\leq C_{s}}$

1. La búsqueda , inserción y eliminación de palabras se realiza en . ^[1] ${\displaystyle O(jD_{\sigma })}$
2. La inserción y eliminación de un simplex completo se realiza en formato . ^[1] ${\displaystyle O(2^{j}D_{\sigma })}$
3. Calcular la homología persistente , o de una manera más complicada, calcular los números de Betti , utilizando un árbol simplex de manera más eficiente sigue siendo un problema abierto; sin embargo, los algoritmos actuales para esta tarea en complejos simpliciales dispersos logran un rendimiento de última generación. ^[4]
4. La estructura de los árboles simplex permite el colapso elemental de los árboles simplex colapsables; sin embargo, se desconocen los límites de esta operación en el caso general. ^{[1] [5] [7]}
5. Un subcaso de colapso elemental es la contracción de bordes . La contracción del borde puede ser

logrado en . ^[1] ${\displaystyle O(kN_{l}^{>j}+C_{s}D_{\sigma })}$

1. La localización de cocaras de un simplex determinado se puede lograr en formato . ^[1] ${\displaystyle O(kN_{l}^{>j})}$
2. La localización de cofacetas de un simplex determinado se puede lograr en . ^[1] ${\displaystyle O(j^{2}D_{\sigma })}$

En cuanto a la construcción, como se ve en la definición constructiva, la construcción es proporcional al número y complejidad de los símplex en el complejo simplicial. Esto puede resultar especialmente caro si el complejo simplicial es denso. Sin embargo, se requieren algunas optimizaciones para complejos simpliciales particulares, incluidos los complejos Flag , los complejos Rips y los complejos Witness. ^{[1] [8]}

Aplicaciones

Los árboles simplex son eficientes en complejos simpliciales dispersos. Para este propósito, muchos algoritmos de homología persistentes que se centran en datos reales de alta dimensión (a menudo escasos) utilizan árboles simplex dentro de estos algoritmos. Si bien los árboles simplex no son tan eficientes como la matriz de incidencia, su estructura basada en simplex les permite ser útiles y eficientes para el almacenamiento complejo simple dentro de algoritmos de homología persistentes. ^[9]

Referencias

1. Boissonnat, Jean-Daniel; María, Clément (noviembre de 2014). "El árbol simplex: una estructura de datos eficiente para complejos generales simpliciales". Algorítmica . 70 (3): 406–427. arXiv : 2001.02581 . doi :10.1007/s00453-014-9887-3. ISSN  0178-4617. S2CID  15335393.
2. Salinas, David (7 de febrero de 2020). "Bloqueador de esqueletos". Comprensión de la geometría en dimensiones superiores . Consultado el 9 de diciembre de 2021 .
3. Godi, Francois (7 de febrero de 2020). "Mapa toplex". Comprensión de la geometría en dimensiones superiores . Consultado el 9 de diciembre de 2021 .
4. Boissonnat, Jean-Daniel. "Manual de referencia del árbol simplex". Comprensión de la geometría en dimensiones superiores . Consultado el 9 de diciembre de 2021 .
5. Piekenbrock, Matt (13 de septiembre de 2020). "simplex_tree: árbol simplex". rdrr.io. ​Consultado el 9 de diciembre de 2021 .
6. Nanda, Vidit. "Perseus, el software de homología persistente". "El proyecto de software Perseus para el cálculo rápido de homología persistente" . Consultado el 9 de diciembre de 2021 .
7. Morozov, Dmitriy (2019). "Lo esencial". Dioniso 2 . Consultado el 9 de diciembre de 2021 .
8. Morozov, Dmitriy (2019). "Complejos de Vietoris-Rips". Dioniso 2 . Consultado el 9 de diciembre de 2021 .
9. Mandal, Sayan (2020). "Aplicaciones de ciclos y homología persistente". La Universidad Estatal de Ohio . Tesis doctoral.