Дискретная теория Морса

Дискретная теория Морса представляет собой комбинаторную адаптацию теории Морса , разработанной Робином Форманом . Теория имеет различные практические применения в различных областях прикладной математики и информатики , таких как конфигурационные пространства , ^[1] гомологии , вычисление ^[2]^[3] шумоподавление , ^[4] сжатие сетки , ^[5] и топологический анализ данных . ^[6]

Обозначения CW комплексов

Позволять $X$ — комплекс CW и обозначим через ${\mathcal {X}}$ свой набор ячеек. Определите функцию инцидентности $\kappa \colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {Z}$ следующим образом: даны две ячейки $\sigma$ и $\tau$ в ${\mathcal {X}}$ , позволять $\kappa (\sigma ,~\tau )$ — степень присоединения отображения к границе $\sigma$ к $\tau$ . Граничный оператор — это эндоморфизм $\partial$ свободной абелевой группы, порожденной ${\mathcal {X}}$ определяется

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

Определяющим свойством граничных операторов является то, что $\partial \circ \partial \equiv 0$ . В более аксиоматических определениях ^[7] можно найти требование, что $\forall \sigma ,\tau ^{\prime }\in {\mathcal {X}}$

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

что является следствием приведенного выше определения граничного оператора и требования, чтобы $\partial \circ \partial \equiv 0$ .

Морса Дискретные функции

функция Действительная $\mu \colon {\mathcal {X}}\to \mathbb {R}$ является дискретной функцией Морса , если она удовлетворяет следующим двум свойствам:

Для любой ячейки $\sigma \in {\mathcal {X}}$ , количество ячеек $\tau \in {\mathcal {X}}$ на границе $\sigma$ которые удовлетворяют $\mu (\sigma )\leq \mu (\tau )$ не более одного.
Для любой ячейки $\sigma \in {\mathcal {X}}$ , количество ячеек $\tau \in {\mathcal {X}}$ содержащий $\sigma$ в их границах, которые удовлетворяют $\mu (\sigma )\geq \mu (\tau )$ не более одного.

Это можно показать ^[8] что мощности в двух условиях не могут одновременно быть одними для фиксированной ячейки $\sigma$ , при условии, что ${\mathcal {X}}$ представляет собой обычный комплекс CW. В этом случае каждая ячейка $\sigma \in {\mathcal {X}}$ может быть сопряжено не более чем с одной исключительной ячейкой $\tau \in {\mathcal {X}}$ : либо граничная ячейка с большим $\mu$ значение или сограничную ячейку с меньшим $\mu$ ценить. Ячейки, не имеющие пар, т. е. значения функций которых строго выше, чем их граничные ячейки , и строго ниже, чем их кограничные ячейки, называются критическими ячейками. Таким образом, дискретная функция Морса делит комплекс CW на три отдельных набора ячеек: ${\mathcal {X}}={\mathcal {A}}\sqcup {\mathcal {K}}\sqcup {\mathcal {Q}}$ , где:

${\mathcal {A}}$ обозначает критические клетки, которые не являются парными,
${\mathcal {K}}$ обозначает ячейки, которые спарены с граничными ячейками, и
${\mathcal {Q}}$ обозначает ячейки, которые соединены в пары с кограничными ячейками.

построению существует биекция множеств между По $k$ -мерные ячейки в ${\mathcal {K}}$ и $(k-1)$ -мерные ячейки в ${\mathcal {Q}}$ , что можно обозначить через $p^{k}\colon {\mathcal {K}}^{k}\to {\mathcal {Q}}^{k-1}$ для каждого натурального числа $k$ . Дополнительным техническим требованием является то, что для каждого $K\in {\mathcal {K}}^{k}$ , степень привязанности отображения от границы $K$ в свою парную ячейку $p^{k}(K)\in {\mathcal {Q}}$ является единицей базовом кольце в ${\mathcal {X}}$ . Например, над целыми числами $\mathbb {Z}$ , единственными допустимыми значениями являются $\pm 1$ . Это техническое требование гарантируется, например, если предположить, что ${\mathcal {X}}$ представляет собой обычный комплекс CW над $\mathbb {Z}$ .

Фундаментальный результат дискретной теории Морса устанавливает, что комплекс CW ${\mathcal {X}}$ изоморфен комплексу на уровне гомологии новому ${\mathcal {A}}$ состоящий только из критических клеток. Парные клетки в ${\mathcal {K}}$ и ${\mathcal {Q}}$ описывают пути градиента между соседними критическими ячейками, которые можно использовать для получения граничного оператора на ${\mathcal {A}}$ . Некоторые подробности этой конструкции представлены в следующем разделе.

Комплекс Морса [ править ]

Градиентный путь — это последовательность парных ячеек.

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

удовлетворяющий $Q_{m}=p(K_{m})$ и $\kappa (K_{m},~Q_{m+1})\neq 0$ . Индекс этого градиентного пути определяется как целое число

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

Деление здесь имеет смысл, поскольку частота встречаемости между парными клетками должна быть $\pm 1$ . Заметим, что по построению значения дискретной функции Морса $\mu$ должно уменьшаться поперек $\rho$ . Путь $\rho$ Говорят, что он соединяет две критические ячейки $A,A'\in {\mathcal {A}}$ если $\kappa (A,Q_{1})\neq 0\neq \kappa (K_{M},A')$ . Эта связь может быть выражена как $A{\stackrel {\rho }{\to }}A'$ . Кратность этого соединения определяется как целое число $m(\rho )=\kappa (A,Q_{1})\cdot \nu (\rho )\cdot \kappa (K_{M},A')$ . Наконец, граничный оператор Морса на критических ячейках ${\mathcal {A}}$ определяется

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

где сумма берется по всем соединениям градиентного пути от $A$ к $A'$ .

Основные результаты

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

Морса Неравенства

Позволять ${\mathcal {A}}$ быть комплексом Морса, связанным с комплексом CW ${\mathcal {X}}$ . Число $m_{q}=|{\mathcal {A}}_{q}|$ из $q$ -клетки в ${\mathcal {A}}$ называется $q$ -е число Морса . Позволять $\beta _{q}$ обозначают $q$ -е Бетти число ${\mathcal {X}}$ . Тогда для любого $N>0$ , следующие неравенства ^[9] держать

m_{N}\geq \beta _{N}

, и

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

Более того, эйлерова характеристика $\chi ({\mathcal {X}})$ из ${\mathcal {X}}$ удовлетворяет

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

гомология Морса и гомотопический Дискретная тип

Позволять ${\mathcal {X}}$ быть регулярным комплексом CW с граничным оператором $\partial$ и дискретная функция Морса $\mu \colon {\mathcal {X}}\to \mathbb {R}$ . Позволять ${\mathcal {A}}$ — ассоциированный комплекс Морса с граничным оператором Морса $\Delta$ . Тогда существует изоморфизм ^[10] гомологии групп

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

и аналогично для гомотопических групп.

Приложения [ править ]

Дискретная теория Морса находит свое применение в анализе формы молекул. ^[11] скелетонирование цифровых изображений/объемов, ^[12] восстановление графиков из зашумленных данных, ^[13] шумоподавление шумных облаков точек ^[14] и анализ каменных орудий в археологии . ^[15]

См. также [ править ]

Ссылки [ править ]

^ Мори, Франческа; Сальветти, Марио (2011), «(Дискретная) теория Морса для конфигурационных пространств» (PDF) , Mathematical Research Letters , 18 (1): 39–57, doi : 10.4310/MRL.2011.v18.n1.a4 , MR 2770581
^ Персей : программное обеспечение постоянной гомологии .
^ Мишайков, Константин; Нанда, Видит (2013). «Теория Морса для фильтрации и эффективное вычисление постоянной гомологии» . Дискретная и вычислительная геометрия . 50 (2): 330–353. дои : 10.1007/s00454-013-9529-6 .
^ Бауэр, Ульрих; Ланге, Карстен; Вардецкий, Макс (2012). «Оптимальное топологическое упрощение дискретных функций на поверхностях» . Дискретная и вычислительная геометрия . 47 (2): 347–377. arXiv : 1001.1269 . дои : 10.1007/s00454-011-9350-z .
^ Левинер, Т.; Лопес, Х.; Таварес, Г. (2004). «Применение дискретной теории Морса Формана к визуализации топологии и сжатию сетки» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 10 (5): 499–508. дои : 10.1109/TVCG.2004.18 . ПМИД 15794132 . S2CID 2185198 . Архивировано из оригинала (PDF) 26 апреля 2012 г.
^ «Набор инструментов топологии» . GitHub.io .
^ Мишайков, Константин; Нанда, Видит (2013). «Теория Морса для фильтрации и эффективное вычисление постоянной гомологии» . Дискретная и вычислительная геометрия . 50 (2): 330–353. дои : 10.1007/s00454-013-9529-6 .
^ Форман 1998 , Лемма 2.5.
^ Форман 1998 , Следствия 3.5 и 3.6.
^ Форман 1998 , Теорема 7.3.
^ Казальс, Ф.; Чазал, Ф.; Левинер, Т. (2003). «Анализ молекулярной формы на основе комплекса Морса-Смейла и функции Коннолли» . Материалы девятнадцатого ежегодного симпозиума по вычислительной геометрии . АКМ Пресс. стр. 351–360. дои : 10.1145/777792.777845 . ISBN 978-1-58113-663-0 . S2CID 1570976 .
^ Дельгадо-Фридрихс, Олаф; Робинс, Ванесса; Шеппард, Адриан (март 2015 г.). «Скелетонизация и разделение цифровых изображений с использованием дискретной теории Морса» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 37 (3): 654–666. дои : 10.1109/TPAMI.2014.2346172 . hdl : 1885/12873 . ISSN 1939-3539 . ПМИД 26353267 . S2CID 7406197 .
^ Дей, Тамал К.; Ван, Цзяюань; Ван, Юсу (2018). Спекманн, Беттина; Тот, Чаба Д. (ред.). Реконструкция графа по дискретной теории Морса . 34-й Международный симпозиум по вычислительной геометрии (SoCG 2018). Международные труды Лейбница по информатике (LIPIcs). Том 99. Дагштуль, Германия: Центр компьютерных наук Schloss Dagstuhl-Leibniz. стр. 31:1–31:15. doi : 10.4230/LIPIcs.SoCG.2018.31 . ISBN 978-3-95977-066-8 . S2CID 3994099 .
^ Мукерджи, Сохам (01 сентября 2021 г.). «Шумоподавление с помощью дискретной теории Морса». Визуальный компьютер . 37 (9): 2883–94. дои : 10.1007/s00371-021-02255-7 . S2CID 237426675 .
^ Булленкамп, Ян Филипп; Линсель, Флориан; Мара, Хуберт (2022), «Идентификация каменных элементов в 3D на основе дискретной теории Морса» , Труды семинара Eurographics по графике и культурному наследию (GCH) , Делфт, Нидерланды: Ассоциация Eurographics, стр. 55–58, doi : 10.2312/ ВАСТ/ВАСТ10/131-138 , ISBN 9783038681786 , ISSN 2312-6124 , S2CID 17294591 , получено 5 октября 2022 г.

Форман, Робин (1998). «Теория Морса для клеточных комплексов» (PDF) . Достижения в математике . 134 (1): 90–145. дои : 10.1006/aima.1997.1650 .
Форман, Робин (2002). «Руководство пользователя по дискретной теории Морса» (PDF) . Семинар по Лотарингской комбинаторике . 48 : Ст. B48c, 35 стр. МР 1939695 .
Козлов, Дмитрий (2007). Комбинаторно-алгебраическая топология . Алгоритмы и вычисления в математике. Том. 21. Спрингер. ISBN 978-3540719618 . МР 2361455 .
Йонссон, Якоб (2007). Симплициальные комплексы графов . Спрингер. ISBN 978-3540758587 .
Орлик, Петр ; Велкер, Фолькмар (2007). Алгебраическая комбинаторика: лекции в летней школе в Нордфьордейде . Университетский текст. Спрингер. дои : 10.1007/978-3-540-68376-6 . ISBN 978-3540683759 . МР 2322081 .
«Дискретная теория Морса» . нЛаб .

[1] Мори, Франческа; Сальветти, Марио (2011), «(Дискретная) теория Морса для конфигурационных пространств» (PDF) , Mathematical Research Letters , 18 (1): 39–57, doi : 10.4310/MRL.2011.v18.n1.a4 , MR 2770581

[2] Персей : программное обеспечение постоянной гомологии .

[3] Мишайков, Константин; Нанда, Видит (2013). «Теория Морса для фильтрации и эффективное вычисление постоянной гомологии» . Дискретная и вычислительная геометрия . 50 (2): 330–353. дои : 10.1007/s00454-013-9529-6 .

[4] Бауэр, Ульрих; Ланге, Карстен; Вардецкий, Макс (2012). «Оптимальное топологическое упрощение дискретных функций на поверхностях» . Дискретная и вычислительная геометрия . 47 (2): 347–377. arXiv : 1001.1269 . дои : 10.1007/s00454-011-9350-z .

[5] Левинер, Т.; Лопес, Х.; Таварес, Г. (2004). «Применение дискретной теории Морса Формана к визуализации топологии и сжатию сетки» (PDF) . Транзакции IEEE по визуализации и компьютерной графике . 10 (5): 499–508. дои : 10.1109/TVCG.2004.18 . ПМИД 15794132 . S2CID 2185198 . Архивировано из оригинала (PDF) 26 апреля 2012 г.

[6] «Набор инструментов топологии» . GitHub.io .

[7] Мишайков, Константин; Нанда, Видит (2013). «Теория Морса для фильтрации и эффективное вычисление постоянной гомологии» . Дискретная и вычислительная геометрия . 50 (2): 330–353. дои : 10.1007/s00454-013-9529-6 .

[8] Форман 1998 , Лемма 2.5.

[9] Форман 1998 , Следствия 3.5 и 3.6.

[10] Форман 1998 , Теорема 7.3.

[11] Казальс, Ф.; Чазал, Ф.; Левинер, Т. (2003). «Анализ молекулярной формы на основе комплекса Морса-Смейла и функции Коннолли» . Материалы девятнадцатого ежегодного симпозиума по вычислительной геометрии . АКМ Пресс. стр. 351–360. дои : 10.1145/777792.777845 . ISBN 978-1-58113-663-0 . S2CID 1570976 .

[12] Дельгадо-Фридрихс, Олаф; Робинс, Ванесса; Шеппард, Адриан (март 2015 г.). «Скелетонизация и разделение цифровых изображений с использованием дискретной теории Морса» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 37 (3): 654–666. дои : 10.1109/TPAMI.2014.2346172 . hdl : 1885/12873 . ISSN 1939-3539 . ПМИД 26353267 . S2CID 7406197 .

[13] Дей, Тамал К.; Ван, Цзяюань; Ван, Юсу (2018). Спекманн, Беттина; Тот, Чаба Д. (ред.). Реконструкция графа по дискретной теории Морса . 34-й Международный симпозиум по вычислительной геометрии (SoCG 2018). Международные труды Лейбница по информатике (LIPIcs). Том 99. Дагштуль, Германия: Центр компьютерных наук Schloss Dagstuhl-Leibniz. стр. 31:1–31:15. doi : 10.4230/LIPIcs.SoCG.2018.31 . ISBN 978-3-95977-066-8 . S2CID 3994099 .

[14] Мукерджи, Сохам (01 сентября 2021 г.). «Шумоподавление с помощью дискретной теории Морса». Визуальный компьютер . 37 (9): 2883–94. дои : 10.1007/s00371-021-02255-7 . S2CID 237426675 .

[EuroGraphicsGCH22-15] Булленкамп, Ян Филипп; Линсель, Флориан; Мара, Хуберт (2022), «Идентификация каменных элементов в 3D на основе дискретной теории Морса» , Труды семинара Eurographics по графике и культурному наследию (GCH) , Делфт, Нидерланды: Ассоциация Eurographics, стр. 55–58, doi : 10.2312/ ВАСТ/ВАСТ10/131-138 , ISBN 9783038681786 , ISSN 2312-6124 , S2CID 17294591 , получено 5 октября 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Обозначения CW ​ комплексов

Морса Дискретные ​ функции