Комбинаторная карта

Комбинаторная карта — это комбинаторное представление графа на ориентируемой поверхности. Комбинаторная карта может также называться комбинаторным вложением , системой вращения , ориентируемым ленточным графом , толстым графом или циклическим графом. ^[1] В более общем смысле, -мерная комбинаторная карта — это комбинаторное представление графа на -мерном ориентируемом многообразии. ${\displaystyle n}$ ${\displaystyle n}$

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

История

Концепция комбинаторной карты была неформально введена Дж. Эдмондсом для многогранных поверхностей ^[2], которые являются планарными графами . Первое определенное формальное выражение под названием «Созвездия» ей дал А. Жак ^{[3] [4],} но эта концепция уже широко использовалась под названием «вращение» Герхардом Рингелем ^[5] и Дж. У. Т. Янгсом в их знаменитом решении проблемы раскраски карт Хивуда. Термин «созвездие» не был сохранен, и вместо него предпочтение было отдано «комбинаторной карте». ^[6]

Комбинаторные карты позднее были обобщены для представления многомерных ориентируемых подразделенных объектов.

Мотивация

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

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

Определение

Комбинаторная карта — это тройка M  = ( D ,  σ ,  α ) такая, что:

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

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

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

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

Многомерное обобщение

n - мерная комбинаторная карта (или n -карта) — это ( n  + 1)-кортеж M  = ( D ,  β ₁ , ...,  β _n ) , такой что: ^{[7] [8]}

• D — конечный набор дротиков;
• β ₁ — перестановка на D ;
• β ₂ , ...,  β _n — инволюции на D ;
• β _i  ∘  β _j является инволюцией, если i  + 2 ≤  j ( i ,  j ∈ { 1, ,...,  n  }) .

n -мерная комбинаторная карта представляет собой подразделение замкнутого ориентируемого n -мерного пространства. Ограничение на β _i  ∘  β _j гарантирует топологическую действительность карты как квазимногообразного подразделения. Двумерные комбинаторные карты можно получить, зафиксировав n  = 2 и переименовав σ в β ₁ , а α в β ₂ .

Пространства, которые не обязательно являются замкнутыми или ориентируемыми, могут быть представлены с помощью ( n -мерных) обобщенных карт .

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

• Полином Боллобаса–Риордана
• Представление границы
• Обобщенные карты
• Двусвязный список ребер
• Структура данных Quad-edge
• Система вращения
• Симплициальный комплекс
• Крылатый край

Ссылки

1. Боллобаш, Бела; Риордан, Оливер (2001). «Полиномиальный инвариант графов на ориентируемых поверхностях». Труды Лондонского математического общества . 83 (3). Wiley: 513–531. doi :10.1112/plms/83.3.513. ISSN  0024-6115. S2CID  15895860.
2. , Дж. (1960). «Комбинаторное представление многогранных поверхностей». Notices Amer. Math. Soc . 7. hdl :1903/24820.
3. Жак, А. (1969). Созвездия и алгебраические топологические графические свойства (доктор философии). Парижский университет.
4. Жак, А. (1970). «Созвездия и топологические графики». Коллок Математика. Соц. Янош Бояи : 657–672.
5. Рингель, Г. (2012) [1974]. Теорема о цвете карты . Спрингер. ISBN 978-3-642-65759-7.
6. Кори, Р. (1975). «Код для планировочных графиков и других приложений». Астериск . 27 . МР  0404045. Збл  0313.05115.
7. Lienhardt, P. (1991). «Топологические модели для представления границ: сравнение с n-мерными обобщенными картами». Computer-Aided Design . 23 (1): 59–82. doi :10.1016/0010-4485(91)90082-8.
8. Lienhardt, P. (1994). «N-мерные обобщенные комбинаторные отображения и клеточные квазимногообразия». International Journal of Computational Geometry and Applications . 4 (3): 275–324. doi :10.1142/S0218195994000173.

Внешние ссылки

• Комбинаторные карты в CGAL , библиотеке алгоритмов вычислительной геометрии:
  • Дамиан, Гийом. "Комбинаторные карты" . Получено 6 февраля 2021 г. .

• Комбинаторные карты в CGoGN , комбинаторное и геометрическое моделирование с универсальными N - мерными картами
• Комбинаторная карта в n Lab