Teoría de Morse discreta

La teoría de Morse discreta es una adaptación combinatoria de la teoría de Morse desarrollada por Robin Forman. La teoría tiene varias aplicaciones prácticas en diversos campos de las matemáticas aplicadas y la informática , como los espacios de configuración , ^[1] el cálculo de homología , ^{[2] [3]} la eliminación de ruido , ^[4] la compresión de mallas , ^[5] y el análisis de datos topológicos . ^[6]

Notación relativa a los complejos CW

Sea un complejo CW y denote por su conjunto de celdas. Defina la función de incidencia de la siguiente manera: dadas dos celdas y en , sea el grado de la función de unión desde el límite de hasta . El operador de límite es el endomorfismo del grupo abeliano libre generado por definido por ${\displaystyle X}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \kappa \colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {Z} }$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \kappa (\sigma ,~\tau )}$ ${\displaystyle \sigma }$ ${\displaystyle \tau }$ ${\displaystyle \partial }$ ${\displaystyle {\mathcal {X}}}$

${\displaystyle \partial (\sigma )=\sum _{\tau \in {\mathcal {X}}}\kappa (\sigma ,\tau )\tau .}$

Es una propiedad definitoria de los operadores de frontera que . En definiciones más axiomáticas ^[7] se puede encontrar el requisito de que ${\displaystyle \partial \circ \partial \equiv 0}$ ${\displaystyle \forall \sigma ,\tau ^{\prime }\in {\mathcal {X}}}$

${\displaystyle \sum _{\tau \in {\mathcal {X}}}\kappa (\sigma ,\tau )\kappa (\tau ,\tau ^{\prime })=0}$

lo cual es una consecuencia de la definición anterior del operador de límite y del requisito de que . ${\displaystyle \partial \circ \partial \equiv 0}$

Funciones Morse discretas

Una función de valor real es una función Morse discreta si satisface las dos propiedades siguientes: ${\displaystyle \mu \colon {\mathcal {X}}\to \mathbb {R} }$

1. Para cualquier celda , el número de celdas en cuyo límite se satisface es como máximo uno. ${\displaystyle \sigma \in {\mathcal {X}}}$ ${\displaystyle \tau \in {\mathcal {X}}}$ ${\displaystyle \sigma }$ ${\displaystyle \mu (\sigma )\leq \mu (\tau )}$
2. Para cualquier celda , el número de celdas que contiene en su límite que satisfacen es como máximo uno. ${\displaystyle \sigma \in {\mathcal {X}}}$ ${\displaystyle \tau \in {\mathcal {X}}}$ ${\displaystyle \sigma }$ ${\displaystyle \mu (\sigma )\geq \mu (\tau )}$

Se puede demostrar ^[8] que las cardinalidades en las dos condiciones no pueden ser una simultáneamente para una celda fija , siempre que sea un complejo CW regular . En este caso, cada celda puede emparejarse con, como máximo, una celda excepcional : ya sea una celda límite con un valor mayor o una celda co-límite con un valor menor. Las celdas que no tienen pares, es decir, cuyos valores de función son estrictamente mayores que sus celdas límite y estrictamente menores que sus celdas co-límite se denominan celdas críticas . Por lo tanto, una función Morse discreta divide el complejo CW en tres conjuntos de celdas distintos: , donde: ${\displaystyle \sigma }$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \sigma \in {\mathcal {X}}}$ ${\displaystyle \tau \in {\mathcal {X}}}$ ${\displaystyle \mu }$ ${\displaystyle \mu }$ ${\displaystyle {\mathcal {X}}={\mathcal {A}}\sqcup {\mathcal {K}}\sqcup {\mathcal {Q}}}$

1. ${\displaystyle {\mathcal {A}}}$denota las células críticas que no están apareadas,
2. ${\displaystyle {\mathcal {K}}}$denota celdas que están emparejadas con celdas límite, y
3. ${\displaystyle {\mathcal {Q}}}$denota células que están emparejadas con células co-limitantes.

Por construcción, hay una biyección de conjuntos entre celdas -dimensionales en y las celdas -dimensionales en , que puede denotarse por para cada número natural . Es un requisito técnico adicional que para cada , el grado de la función adjunta desde el límite de hasta su celda emparejada sea una unidad en el anillo subyacente de . Por ejemplo, sobre los enteros , los únicos valores permitidos son . Este requisito técnico se garantiza, por ejemplo, cuando se supone que es un complejo CW regular sobre . ${\displaystyle k}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle (k-1)}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle p^{k}\colon {\mathcal {K}}^{k}\to {\mathcal {Q}}^{k-1}}$ ${\displaystyle k}$ ${\displaystyle K\in {\mathcal {K}}^{k}}$ ${\displaystyle K}$ ${\displaystyle p^{k}(K)\in {\mathcal {Q}}}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \pm 1}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \mathbb {Z} }$

El resultado fundamental de la teoría de Morse discreta establece que el complejo CW es isomorfo en el nivel de homología con un nuevo complejo que consta únicamente de las celdas críticas. Las celdas pareadas en y describen trayectorias de gradiente entre celdas críticas adyacentes que se pueden utilizar para obtener el operador de frontera en . En la siguiente sección se proporcionan algunos detalles de esta construcción. ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathcal {A}}}$

El complejo Morse

Una ruta de gradiente es una secuencia de celdas emparejadas

${\displaystyle \rho =(Q_{1},K_{1},Q_{2},K_{2},\ldots ,Q_{M},K_{M})}$

satisfactorio y . El índice de esta ruta de gradiente se define como el entero ${\displaystyle Q_{m}=p(K_{m})}$ ${\displaystyle \kappa (K_{m},~Q_{m+1})\neq 0}$

${\displaystyle \nu (\rho )={\frac {\prod _{m=1}^{M-1}-\kappa (K_{m},Q_{m+1})}{\prod _{m=1}^{M}\kappa (K_{m},Q_{m})}}.}$

La división aquí tiene sentido porque la incidencia entre celdas pareadas debe ser . Nótese que por construcción, los valores de la función de Morse discreta deben disminuir a lo largo de . Se dice que la ruta conecta dos celdas críticas si . Esta relación puede expresarse como . La multiplicidad de esta conexión se define como el entero . Finalmente, el operador de frontera de Morse en las celdas críticas se define como ${\displaystyle \pm 1}$ ${\displaystyle \mu }$ ${\displaystyle \rho }$ ${\displaystyle \rho }$ ${\displaystyle A,A'\in {\mathcal {A}}}$ ${\displaystyle \kappa (A,Q_{1})\neq 0\neq \kappa (K_{M},A')}$ ${\displaystyle A{\stackrel {\rho }{\to }}A'}$ ${\displaystyle m(\rho )=\kappa (A,Q_{1})\cdot \nu (\rho )\cdot \kappa (K_{M},A')}$ ${\displaystyle {\mathcal {A}}}$

${\displaystyle \Delta (A)=\kappa (A,A')+\sum _{A{\stackrel {\rho }{\to }}A'}m(\rho )A'}$

donde se toma la suma de todas las conexiones de ruta de gradiente desde hasta . ${\displaystyle A}$ ${\displaystyle A'}$

Resultados básicos

Muchos de los resultados conocidos de la teoría de Morse continua se aplican en el entorno discreto.

Las desigualdades de Morse

Sea un complejo de Morse asociado al complejo CW . El número de celdas en se denomina -ésimo número de Morse . Sea denotado el -ésimo número de Betti de . Entonces, para cualquier , se cumplen las siguientes desigualdades ^[9] ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle m_{q}=|{\mathcal {A}}_{q}|}$ ${\displaystyle q}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle q}$ ${\displaystyle \beta _{q}}$ ${\displaystyle q}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle N>0}$

${\displaystyle m_{N}\geq \beta _{N}}$, y

${\displaystyle m_{N}-m_{N-1}+\dots \pm m_{0}\geq \beta _{N}-\beta _{N-1}+\dots \pm \beta _{0}}$

Además, la característica de Euler de satisface ${\displaystyle \chi ({\mathcal {X}})}$ ${\displaystyle {\mathcal {X}}}$

${\displaystyle \chi ({\mathcal {X}})=m_{0}-m_{1}+\dots \pm m_{\dim {\mathcal {X}}}}$

Homología de Morse discreta y tipo de homotopía

Sea un complejo CW regular con operador de frontera y una función de Morse discreta . Sea el complejo de Morse asociado con operador de frontera de Morse . Entonces, existe un isomorfismo ^[10] de grupos de homología ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \partial }$ ${\displaystyle \mu \colon {\mathcal {X}}\to \mathbb {R} }$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \Delta }$

${\displaystyle H_{*}({\mathcal {X}},\partial )\simeq H_{*}({\mathcal {A}},\Delta ),}$

y lo mismo para los grupos de homotopía.

Aplicaciones

La teoría de Morse discreta encuentra su aplicación en el análisis de formas moleculares, ^[11] la esqueletización de imágenes/volúmenes digitales, ^[12] la reconstrucción de gráficos a partir de datos ruidosos, ^[13] la eliminación de ruido de nubes de puntos ruidosas ^[14] y el análisis de herramientas líticas en arqueología . ^[15]

Véase también

• Teoría del código Morse digital
• Teoría de Morse estratificada
• Análisis de forma
• Combinatoria topológica
• Geometría diferencial discreta

Referencias

1. Mori, Francesca; Salvetti, Mario (2011), "Teoría de Morse (discreta) para espacios de configuración" (PDF) , Mathematical Research Letters , 18 (1): 39–57, doi : 10.4310/MRL.2011.v18.n1.a4 , MR  2770581
2. Perseo: el software de homología persistente .
3. Mischaikow, Konstantin; Nanda, Vidit (2013). "Teoría de Morse para filtraciones y cálculo eficiente de homología persistente". Geometría discreta y computacional . 50 (2): 330–353. doi : 10.1007/s00454-013-9529-6 .
4. Bauer, Ulrich; Lange, Carsten; Wardetzky, Max (2012). "Simplificación topológica óptima de funciones discretas en superficies". Geometría discreta y computacional . 47 (2): 347–377. arXiv : 1001.1269 . doi : 10.1007/s00454-011-9350-z .
5. Lewiner, T.; Lopes, H.; Tavares, G. (2004). "Aplicaciones de la teoría discreta de Morse de Forman a la visualización de topología y compresión de mallas" (PDF) . IEEE Transactions on Visualization and Computer Graphics . 10 (5): 499–508. doi :10.1109/TVCG.2004.18. PMID  15794132. S2CID  2185198. Archivado desde el original (PDF) el 26 de abril de 2012.
6. "El kit de herramientas de topología". GitHub.io .
7. Mischaikow, Konstantin; Nanda, Vidit (2013). "Teoría de Morse para filtraciones y cálculo eficiente de homología persistente". Geometría discreta y computacional . 50 (2): 330–353. doi : 10.1007/s00454-013-9529-6 .
8. Forman 1998, Lema 2.5
9. Forman 1998, Corolarios 3.5 y 3.6
10. Forman 1998, Teorema 7.3
11. Cazals, F.; Chazal, F.; Lewiner, T. (2003). "Análisis de la forma molecular basado en el complejo de Morse-Smale y la función de Connolly". Actas del decimonoveno simposio anual sobre geometría computacional . ACM Press. págs. 351–360. doi :10.1145/777792.777845. ISBN 978-1-58113-663-0.S2CID 1570976  .
12. Delgado-Friedrichs, Olaf; Robins, Vanessa; Sheppard, Adrian (marzo de 2015). "Esqueletización y partición de imágenes digitales utilizando la teoría de Morse discreta". IEEE Transactions on Pattern Analysis and Machine Intelligence . 37 (3): 654–666. doi :10.1109/TPAMI.2014.2346172. hdl : 1885/12873 . ISSN  1939-3539. PMID  26353267. S2CID  7406197.
13. Dey, Tamal K.; Wang, Jiayuan; Wang, Yusu (2018). Speckmann, Bettina; Tóth, Csaba D. (eds.). Reconstrucción de grafos mediante la teoría de Morse discreta. 34.° Simposio internacional sobre geometría computacional (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 99. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. págs. 31:1–31:15. doi : 10.4230/LIPIcs.SoCG.2018.31 . ISBN 978-3-95977-066-8. Número de identificación del sujeto  3994099.
14. Mukherjee, Soham (1 de septiembre de 2021). "Eliminación de ruido con teoría de Morse discreta". The Visual Computer . 37 (9): 2883–94. doi :10.1007/s00371-021-02255-7. S2CID  237426675.
15. Bullenkamp, ​​Jan Philipp; Linsel, Florian; Mara, Hubert (2022), "Identificación de características líticas en 3D basada en la teoría de Morse discreta", Actas del Taller Eurographics sobre gráficos y patrimonio cultural (GCH) , Delft, Países Bajos: Eurographics Association, págs. 55–58, doi :10.2312/VAST/VAST10/131-138, ISBN 9783038681786, ISSN  2312-6124, S2CID  17294591 , consultado el 5 de octubre de 2022

• Forman, Robin (1998). "Teoría de Morse para complejos celulares" (PDF) . Avances en Matemáticas . 134 (1): 90–145. doi : 10.1006/aima.1997.1650 .
• Forman, Robin (2002). "Una guía del usuario para la teoría Morse discreta" (PDF) . Seminario Lotharingien de Combinatoire . 48 : Arte. B48c, 35 págs. SEÑOR  1939695.
• Kozlov, Dmitry (2007). Topología algebraica combinatoria . Algoritmos y computación en matemáticas. Vol. 21. Springer. ISBN 978-3540719618.Señor 2361455  .
• Jonsson, Jakob (2007). Complejos simpliciales de grafos . Springer. ISBN 978-3540758587.
• Orlik, Peter ; Welker, Volkmar (2007). Combinatoria algebraica: conferencias en una escuela de verano en Nordfjordeid . Universitext. Springer. doi :10.1007/978-3-540-68376-6. ISBN 978-3540683759.Señor 2322081  .
• "Teoría de Morse discreta". nLab .