Комбинаторная карта - Combinatorial map

А комбинаторное отображение это комбинаторный объектное моделирование топологический конструкции с подразделениями. Исторически концепция была введена неформально Дж. Эдмондс за многогранные поверхности ^[1] которые планарные графы. Первое определенное формальное выражение он получил под названием «Созвездия» А. Жаком. ^[2] но эта концепция уже широко использовалась под названием «вращение» Герхард Рингель^[3] и J.W.T. Янгса в их знаменитом решении проблемы раскраски карты Хивуда. Термин «созвездие» не был сохранен, и вместо него предпочтение было отдано «комбинаторной карте». Позднее эта концепция была расширена для представления ориентируемых подразделенных объектов более высоких измерений. Комбинаторные карты используются в качестве эффективных структур данных в представлении изображений и обработка, в геометрическом моделировании. Эта модель связана с симплициальные комплексы и чтобы комбинаторная топология. Обратите внимание, что комбинаторные отображения были расширены на обобщенные карты которые позволяют также представлять неориентируемые объекты, такие как Лента Мебиуса и Бутылка Клейна. Комбинаторное отображение - это граничное представление модель; он представляет объект своими границами.

Мотивация

Некоторым приложениям требуется структура данных для представления подразделения объекта. Например, 2D-объект может быть разложен на вершины (0-ячейки), ребра (1-ячейки) и грани (2-ячейки). В более общем смысле, n-мерный объект состоит из ячеек размером от 0 до n. Более того, также часто необходимо представить отношения соседства между этими ячейками.

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

Представление плоского графа

Первые работы о комбинаторных отображениях^[4]^[5] разработать комбинаторные представления графов на поверхностях, которые включают планарные графы: Двумерное комбинаторное отображение (или двумерное отображение) является триплетом M = (D, σ, α) такой, что:

D конечный набор дротиков;
σ это перестановка на D;
α является инволюция на D без фиксированной точки.

Интуитивно, 2-карта соответствует планарному графу, в котором каждое ребро разделено на два дротика (иногда также называемых полуребрами). Перестановка σ дает для каждого дротика следующий дротик, вращая вершину в положительной ориентации; другая перестановка α дает для каждого дротика другой дротик с тем же краем.

α позволяет извлекать ребра (аlpha для аrête на французском языке), и σ позволяет извлекать вершины (sigma для sommet на французском языке). Мы определяем φ = σ о α что дает для каждого дротика следующий дротик с той же гранью (ппривет для жace также на французском языке).

Итак, есть два способа представить комбинаторную карту в зависимости от того, является ли перестановка σ или же φ (см. пример ниже). Эти два представления двойственны друг другу: вершины и грани меняются местами.

**Пример комбинаторных карт**: плоский граф и два комбинаторных отображения в зависимости от использования обозначений (D, σ, α) или же (D, φ, α).
Плоский граф	Соответствующее комбинаторное отображение (D, σ, α). Дротики представлены пронумерованными сегментами, σ серыми стрелками (пример σ(1) = 7), два дротика соединены α нарисованы последовательно и разделены небольшой полосой (пример α(1)=2).	Соответствующее комбинаторное отображение (D, φ, α). Дротики представлены пронумерованными стрелками, два дротика соединены φ рисуются последовательно (пример φ(1) = 3) и два дротика, соединенных α нарисованы параллельно и в обратной ориентации (пример α(1)=2).

Общее определение

Определение комбинаторного отображения в любой размерности следующее.^[6]^[7]

An п-мерное комбинаторное отображение (или п-map) - это (п + 1) -часть M = (D, β₁, ..., β_п) такой, что:

D конечный набор дротиков;
β₁ это перестановка на D;
β₂, ..., β_п находятся инволюции на D;
β_я оβ_j инволюция, если я + 2 ≤ j (я, j ∈ { 1, ,..., п }).

An п-мерное комбинаторное отображение представляет собой подразделение замкнутой ориентируемой п-мерное пространство. Дротик - это абстрактный элемент, который требуется только для определения однозначных отображений. Последняя строка этого определения фиксирует ограничения, которые гарантируют топологическую достоверность представленного объекта: комбинаторное отображение представляет собой подразделение квазимногообразия. Исходное определение двумерных комбинаторных отображений можно получить, зафиксировав п = 2 и переименование σ к β₁ и α к β₂.

Смотрите также

внешняя ссылка

Комбинаторные отображения в CGAL, Библиотека алгоритмов вычислительной геометрии:
- Дамиан, Гийом. «Комбинаторные карты». Проверено октябрь 2011 г.. Проверить значения даты в: | accessdate = (помощь)

Комбинаторные отображения в CGoGN, Cомбинаторные и граммeometric mовозиться с граммэнергичный N-размерный Mапс
Комбинаторная карта в nLab

[1] Эдмондс Дж. Комбинаторное представление многогранных поверхностей, Примечания Amer. Математика. Soc., Т. 7 августа 1960 г.

[2] Жак А., Constellations et Graphes Topologiques, Colloque Math. Soc. Янош Бойяи, стр. 657-672, 1970

[3] Рингель Г. Теорема о цвете карт, Springer-Verlag, Берлин, 1974.

[4] Жак, А. Constellations et propriétés algébriques des graphes topologiques, доктор философии. дипломная работа, Париж, 1969 г.

[5] Кори Р., Код ООН для плоских графиков и приложений, Astérisque, т. 27 августа 1975 г.

[6] Линхардт П. Топологические модели для граничного представления: сравнение с п-мерные обобщенные отображения, Системы автоматизированного проектирования, Vol. 23, № 1, стр. 59-82, 1991

[7] Линхардт П., N-мерные обобщенные комбинаторные отображения и клеточные квазимногообразия, Международный журнал вычислительной геометрии и приложений, Vol. 4, вып. 3. С. 275-324, 1994.

[1]

[2]

[3]

[4]

[5]

[6]

[7]