Kombinatorická mapa - Combinatorial map
A kombinatorická mapa je kombinační modelování objektů topologické struktury s rozdělenými objekty. Historicky byl koncept představen neformálně J. Edmonds pro polyedrické povrchy [1] což jsou rovinné grafy. První definitivní formální výraz dostal pod jménem „Constellations“ od A. Jacquesa [2] ale koncept již byl široce používán pod názvem "rotace" od Gerhard Ringel[3] a J.W.T. Youngs in their famous solution of the Heawood map-colored problem. Termín „souhvězdí“ nebyl zachován a místo toho byl upřednostňován „kombinatorický mapa“. Koncept byl později rozšířen tak, aby představoval výškově orientovatelné rozdělené objekty. Kombinatorické mapy se používají jako efektivní datové struktury v obrazové reprezentaci a zpracovává se, v geometrickém modelování. Tento model souvisí s zjednodušené komplexy a do kombinatorická topologie. Všimněte si, že kombinatorické mapy byly rozšířeny na zobecněné mapy které umožňují také reprezentovat neorientovatelné objekty, jako je Möbiusův proužek a Kleinova láhev. Kombinatorická mapa je a hraniční reprezentace Modelka; představuje objekt svými hranicemi.
Motivace
Několik aplikací vyžaduje datovou strukturu, která představuje dělení objektu. Například 2D objekt lze rozložit na vrcholy (0 buněk), hrany (1 buňky) a plochy (2 buňky). Obecněji řečeno, n-dimenzionální objekt je složen z buněk o dimenzi 0 až n. Kromě toho je také často nutné představovat sousední vztahy mezi těmito buňkami.
Chceme tedy popsat všechny buňky dělení plus všechny vztahy výskytu a sousedství mezi těmito buňkami. Když jsou všechny reprezentované buňky simplexy, a zjednodušený komplex lze použít, ale když chceme reprezentovat jakýkoli typ buněk, musíme použít buněčné topologické modely, jako jsou kombinatorické mapy nebo zobecněné mapy.
Reprezentace rovinného grafu
První práce o kombinatorických mapách[4][5] vyvinout kombinatorické znázornění grafů na plochách, které zahrnuje rovinné grafy: 2-dimenzionální kombinatorická mapa (nebo 2-mapa) je triplet M = (D, σ, α) takové, že:
Intuitivně odpovídá 2-mapa rovinnému grafu, kde je každá hrana rozdělena na dvě šipky (někdy také nazývané poloviční hrany). Obměna σ dává pro každou šipku další šipku otáčením kolem vrcholu v pozitivní orientaci; druhá permutace α dává pro každou šipku druhou šipku se stejným okrajem.
α umožňuje získat hrany (Alpha pro Arête ve francouzštině) a σ umožňuje načíst vrcholy (sigma pro sommet ve francouzštině). Definujeme φ = σ Ó α což dává pro každou šipku další šipku stejné tváře (pahoj pro Feso také ve francouzštině).
Existují tedy dva způsoby, jak reprezentovat kombinatorickou mapu v závislosti na tom, zda je permutace σ nebo φ (viz příklad níže). Tyto dvě reprezentace jsou navzájem dvojí: vrcholy a tváře se vyměňují.
![]() Rovinný graf | ![]() Odpovídající kombinatorická mapa (D, σ, α). Šipky jsou reprezentovány očíslovanými segmenty, σ šedými šipkami (příklad σ(1) = 7), dvě šipky propojené α jsou kresleny postupně a jsou odděleny malou lištou (příklad α(1)=2). | ![]() Odpovídající kombinatorická mapa (D, φ, α). Šipky jsou reprezentovány očíslovanými šipkami, dvě šipky spojené φ jsou kresleny postupně (příklad φ(1) = 3) a dvě šipky propojené pomocí α jsou nakresleny paralelně a v obrácené orientaci (příklad α(1)=2). |
Obecná definice
Definice kombinatorické mapy v jakékoli dimenzi je následující.[6][7]
An n-dimenzionální kombinatorická mapa (nebo n-map) je (n + 1) -tuple M = (D, β1, ..., βn) takové, že:
- D je konečná sada šipek;
- β1 je permutace na D;
- β2, ..., βn jsou involuce na D;
- βi Óβj je involuce, pokud i + 2 ≤ j (i, j ∈ { 1, ,..., n }).
An n-dimenzionální kombinatorická mapa představuje dělení uzavřené orientovatelné n-rozměrný prostor. Šipka je abstraktní prvek, který je vyžadován pouze k definování mapování 1: 1. Poslední řádek této definice opravuje omezení, která zaručují topologickou platnost představovaného objektu: kombinatorická mapa představuje kvazi-rozmanité dělení. Počáteční definici 2-dimenzionálních kombinatorických map lze získat opravou n = 2 a přejmenování σ podle β1 a α podle β2.
Viz také
- Hraniční reprezentace
- Zobecněné mapy
- Dvojnásobně spojený seznam hran
- Quad-edge datová struktura
- Rotační systém
- Zjednodušený komplex
- Okřídlený okraj
Reference
- ^ Edmonds J., Kombinatorické znázornění polyhedrálních povrchů, sdělení Amer. Matematika. Soc., Sv. 7, 1960
- ^ Jacques A., Constellations et Graphes Topologiques, Colloque Math. Soc. János Bolyai, str. 657-672, 1970
- ^ Ringel G., Věta o barevné mapě, Springer-Verlag, Berlín 1974
- ^ Jacques, A. Constellations et propriétés algébriques des graphes topologiques, Ph.D. práce, Paříž 1969
- ^ Cori R., Un code pour les graphes planaires et ses applications, Astérisque, sv. 27, 1975
- ^ Lienhardt P., Topologické modely pro hraniční reprezentaci: srovnání s n-rozměrné zobecněné mapy, Počítačem podporovaný design, Sv. 23, č. 1, str. 59-82, 1991
- ^ Lienhardt P., N-dimenzionální generalizované kombinatorické mapy a buněčné kvazi-varietá, International Journal on Computational Geometry and Applications, Vol. 4, č. 3, str. 275-324, 1994
externí odkazy
- Kombinatorické mapy v CGAL, Knihovna algoritmů výpočetní geometrie:
- Damiand, Guillaume. „Kombinatorické mapy“. Vyvolány October 2011. Zkontrolujte hodnoty data v:
| accessdate =
(Pomoc)
- Damiand, Guillaume. „Kombinatorické mapy“. Vyvolány October 2011. Zkontrolujte hodnoty data v:
- Kombinatorické mapy v CGoGN, Combinatorial a Geometrický mÓprocházet s Generic N-dimenzionální Maps
- Kombinatorická mapa v nLab