Из Википедии, бесплатной энциклопедии
  (Перенаправлено с комбинаторных карт )
Перейти к навигации Перейти к поиску

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

Мотивация [ править ]

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

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

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

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

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

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

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

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

Общее определение [ править ]

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

П - мерная комбинаторная карта (или п -map) является ( п  + 1) -кратный М  = ( D ,  β 1 , ...,  β п ) таким образом, что:

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

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

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

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

  1. ^ Эдмондс Дж. Комбинаторное представление многогранных поверхностей, Примечания Amer. Математика. Soc., Т. 7 августа 1960 г.
  2. ^ Жак А., Constellations et Graphes Topologiques, Colloque Math. Soc. Янош Бойяи, стр. 657-672, 1970
  3. ^ Рингель Г., Теорема цвета карты, Springer-Verlag, Берлин 1974
  4. ^ Жак, A. Constellations et propriétés algébriques des graphes topologiques, доктор философии. дипломная работа, Париж, 1969 г.
  5. ^ Кори Р., Код ООН для плоских графиков и приложений, Astérisque, т. 27 августа 1975 г.
  6. ^ Линхардт П., Топологические модели для граничного представления: сравнение с n- мерными обобщенными отображениями, Computer-Aided Design , Vol. 23, № 1, стр. 59-82, 1991
  7. ^ Линхардт П., N-мерные обобщенные комбинаторные отображения и клеточные квазимногообразия, Международный журнал вычислительной геометрии и приложений, Vol. 4, вып. 3. С. 275-324, 1994.

Внешние ссылки [ править ]

  • Комбинаторные карты в CGAL , библиотеке алгоритмов вычислительной геометрии:
    • Дамиан, Гийом. «Комбинаторные карты» . Проверено 6 февраля 2021 года .
  • Комбинаторные карты в CGoGN , C ombinatorial и G eometric м O deling с G eneric N - мерный М АФСОМ
  • Комбинаторная карта в nLab