График Риба - Reeb graph

График Риба функции высоты на торе.

А График Риба[1] (названный в честь Жорж Риб к Рене Том ) это математический объект, отражающий эволюцию наборы уровней ценного функция на многообразие.[2]В соответствии с [3] аналогичная концепция была введена Г. Адельсон-Вельский и В КАЧЕСТВЕ. Кронрод и применяется для анализа Тринадцатая проблема Гильберта.[4] Предложено Г. Рибом в качестве инструмента в Теория Морса,[5] Графы Риба - естественный инструмент для изучения многозначных функциональных взаимосвязей между двумерными скалярными полями. , , и вытекающие из условий и , потому что эти отношения однозначны, когда они ограничены областью, связанной с отдельным ребром графа Риба. Этот общий принцип был впервые использован для изучения нейтральные поверхности в океанография.[6]

Графики Риба также нашли широкое применение в вычислительная геометрия и компьютерная графика,[1][7] включая компьютерный геометрический дизайн, топология -основан соответствие формы,[8][9][10] анализ топологических данных,[11] топологическое упрощение и очистка, сегментация поверхностей [12] и параметризация, эффективное вычисление наборов уровней и геометрические термодинамика.[3]В частном случае функции на плоском пространстве (технически односвязной области) граф Риба образует многодерево и также называется контурное дерево.[13]

Справка по графикам набора уровней статистические выводы связанные с оценкой функции плотности вероятности и регресс функции, и их можно использовать в кластерный анализ и функция оптимизация, среди прочего. [14]

Формальное определение

Учитывая топологическое пространство Икс и непрерывная функция ж: Икс → ропределить отношение эквивалентности ∼ на Икс куда п∼q в любое время п и q принадлежат к тому же связный компонент одного набор уровней ж−1(c) для некоторых реальных c. В График Риба это факторное пространство Икс / ∼ с фактор-топологией.

Описание функций Морзе

Если ж это Функция Морса с четким критические значения, граф Риба можно описать более явно. Его узлы, или вершины, соответствуют множествам критических уровней ж−1(c). Шаблон, в котором дуги или ребра пересекаются в узлах / вершинах, отражает изменение топологии набора уровней. ж−1(т) в качестве т проходит через критическое значение c. Например, если c это минимум или максимум ж, компонент создан или уничтожен; следовательно, дуга начинается или заканчивается в соответствующем узле, который имеет степень 1. Если c это точка перевала индекса 1 и двух компонентов ж−1(т) слить в т = c в качестве т увеличивается, соответствующая вершина графа Риба имеет степень 3 и имеет вид буквы «Y»; те же рассуждения применимы, если индекс c тусклоИкс−1 и компонент ж−1(c) делится на два.

Рекомендации

  1. ^ а б Ю. Синагава, Т. Куний, Ю.Л. Kergosien, 1991. Поверхностное кодирование на основе теории Морса. IEEE Computer Graphics and Applications, 11 (5), pp.66-78.
  2. ^ Хариш Дорайсвами, Виджай Натараджан, Эффективные алгоритмы вычисления графиков Риба, Вычислительная геометрия 42 (2009) 606–616
  3. ^ а б Горбань, Александр Н. (2013). «Термодинамическое дерево: пространство допустимых путей». Журнал SIAM по прикладным динамическим системам. 12 (1): 246–278. arXiv:1201.6315. Дои:10.1137/120866919.
  4. ^ Адельсон-Вельский Г. М., Кронрод А. С. О множествах уровня непрерывных функций с частными производными, Докл. Акад. АН СССР, 49 (4) (1945), с. 239–241.
  5. ^ G. Reeb, Sur les points singuliers d’une forme de Pfaff Complètement intégrable ou d’une fonction numérique, C.R. Acad. Sci. Париж 222 (1946) 847–849
  6. ^ Стэнли, Джеффри Дж. (Июнь 2019 г.). «Топология нейтральной поверхности». Моделирование океана. 138: 88–106. arXiv:1903.10091. Дои:10.1016 / j.ocemod.2019.01.008.
  7. ^ Ю. Синагава, Т.Л. Куний, 1991. Автоматическое построение графа Риба из сечений. IEEE Computer Graphics and Applications, 11 (6), pp.44-51.
  8. ^ Паскуччи, Валерио; Скорцелли, Джорджио; Бремер, Пер-Тимо; Маскаренхас, Аджит (2007). «Надежное онлайн-вычисление графиков Риба: простота и скорость» (PDF). Транзакции ACM на графике. 26 (3): 58.1–58.9. Дои:10.1145/1276377.1276449.
  9. ^ М. Хилага, Ю. Синагава, Т. Кохмура, Т.Л. Куний, 2001, август. Согласование топологии для полностью автоматической оценки подобия 3D-форм. В материалах 28-й ежегодной конференции по компьютерной графике и интерактивным методам (стр. 203-212). ACM.
  10. ^ Тунг, Тони; Шмитт, Фрэнсис (2005). «Подход с использованием расширенного графа Reeb с множественным разрешением для извлечения трехмерных фигур на основе содержимого». Международный журнал моделирования форм. 11 (1): 91–120. Дои:10.1142 / S0218654305000748.
  11. ^ «Набор инструментов топологии».
  12. ^ Хаджидж, Мустафа; Розен, Пол (2020). «Эффективный алгоритм параллельного поиска данных на основе графа Риба». MDPI. 13: 258. Дои:10.3390 / a13100258.
  13. ^ Карр, Хэмиш; Snoeyink, Джек; Аксен, Ульрике (2000), «Вычисление контурных деревьев во всех измерениях», Proc. 11-й симпозиум ACM-SIAM по дискретным алгоритмам (SODA 2000), стр. 918–926.
  14. ^ Клемеля, Юсси (2018). «Методы дерева наборов уровней». Междисциплинарные обзоры Wiley: вычислительная статистика. 10 (5): e1436. Дои:10.1002 / wics.1436.