Mapa combinatorio

Un mapa combinatorio es un objeto combinatorio que modela estructuras topológicas con objetos subdivididos. Históricamente, el concepto fue introducido informalmente por J. Edmonds para superficies poliédricas ^[1] que son gráficas planas . Se le dio su primera expresión formal definida bajo el nombre de "Constelaciones" por A. Jacques ^[2] pero el concepto ya fue ampliamente utilizado bajo el nombre de "rotación" por Gerhard Ringel ^[3].y JWT Youngs en su famosa solución del problema de colorear mapas de Heawood. El término "constelación" no se mantuvo y en su lugar se prefirió "mapa combinatorio". El concepto se amplió más tarde para representar objetos subdivididos orientables de dimensiones superiores. Los mapas combinatorios se utilizan como estructuras de datos eficientes en la representación y el procesamiento de imágenes , en el modelado geométrico. Este modelo está relacionado con los complejos simpliciales y con la topología combinatoria . Tenga en cuenta que los mapas combinatorios se extendieron a mapas generalizados que también permiten representar objetos no orientables como la tira de Möbius y la botella de Klein . Un mapa combinatorio es una representación de límitesmodelo; representa el objeto por sus límites.

Un mapa combinatorio es equivalente a un sistema de rotación , ya que ambos representan gráficos incrustados orientablemente.

Motivación

Varias aplicaciones requieren una estructura de datos para representar la subdivisión de un objeto. Por ejemplo, un objeto 2D se puede descomponer en vértices (celdas 0), aristas (celdas 1) y caras (2 celdas). De manera más general, un objeto n-dimensional se compone de celdas de dimensión 0 an. Además, a menudo también es necesario representar relaciones vecinas entre estas células.

Por lo tanto, queremos describir todas las celdas de la subdivisión, más todas las relaciones de incidencia y adyacencia entre estas celdas. Cuando todas las celdas representadas son simplex, se puede usar un complejo simplicial , pero cuando queremos representar cualquier tipo de celdas, necesitamos usar modelos topológicos celulares como mapas combinatorios o mapas generalizados.

Representación gráfica plana

Los primeros trabajos sobre mapas combinatorios ^{[4] [5]} desarrollan representaciones combinatorias de gráficos en superficies que incluyen gráficos planos : Un mapa combinatorio bidimensional (o mapa bidimensional) es un triplete M  = ( D ,  σ ,  α ) tal que :

• D es un juego finito de dardos;
• σ es una permutación de D ;
• α es una involución en D sin punto fijo.

Intuitivamente, un mapa de 2 corresponde a un gráfico plano donde cada borde se subdivide en dos dardos (a veces también llamados medios bordes). La permutación σ da, para cada dardo, el próximo dardo girando el vértice en la orientación positiva; la otra permutación α da, para cada dardo, el otro dardo del mismo borde.

α permite a uno para recuperar bordes ( un lpha para un rete en francés), y σ le permite a uno para recuperar vértices ( s IGMA para s ommet en francés). Definimos φ  =  σ o α que da, para cada dardo, el próximo dardo de la misma cara ( p hi para f ace también en francés).

Entonces, hay dos formas de representar un mapa combinatorio dependiendo de si la permutación es σ o φ (ver ejemplo a continuación). Estas dos representaciones son duales entre sí: se intercambian vértices y caras.

Ejemplo de mapas combinatorios : un gráfico plano y los dos mapas combinatorios dependiendo de si usamos la notación ( D ,  σ ,  α ) o ( D ,  φ ,  α ).

Un gráfico plano

Mapa combinatorio correspondiente ( D ,  σ ,  α ). Los dardos están representados por segmentos numerados, σ por flechas grises (ejemplo σ (1) = 7), dos dardos enlazados por α se dibujan consecutivamente y separados por una pequeña barra (ejemplo α (1) = 2).

Mapa combinatorio correspondiente ( D ,  φ ,  α ). Los dardos están representados por flechas numeradas, dos dardos enlazados por φ se dibujan consecutivamente (ejemplo φ (1) = 3) y dos dardos enlazados por α se dibujan en paralelo y en orientación inversa (ejemplo α (1) = 2).

Definición general

La definición de mapa combinatorio en cualquier dimensión es la siguiente. ^{[6] [7]}

Un mapa combinatorio n- dimensional (o n- mapa) es una ( n  + 1) -tupla M  = ( D ,  β ₁ , ...,  β _n ) tal que:

• D es un juego finito de dardos;
• β ₁ es una permutación de D ;
• β ₂ , ...,  β _n son involuciones en D ;
• β _i  o  β _j es una involución si i  + 2 ≤  j ( i ,  j ∈ {1,, ...,  n  }).

Un mapa combinatorio n- dimensional representa la subdivisión de un espacio n- dimensional orientable cerrado . Un dardo es un elemento abstracto que solo se requiere para definir asignaciones uno a uno. La última línea de esta definición fija restricciones que garantizan la validez topológica del objeto representado: un mapa combinatorio representa una subdivisión cuasi-múltiple. La definición inicial de mapas combinatorios bidimensionales se puede recuperar fijando n  = 2 y cambiando el nombre de σ por β ₁ y α por β ₂ .

Ver también

• Representación de límites
• Mapas generalizados
• Lista de bordes doblemente conectados
• Estructura de datos de cuatro bordes
• Sistema de rotacion
• Complejo simplicial
• Borde alado

Referencias

1. Edmonds J., Una representación combinatoria de superficies poliédricas, Avisos Amer. Matemáticas. Soc., Vol. 7 de 1960
2. Jacques A., Constellations et Graphes Topologiques, Colloque Math. Soc. János Bolyai, pág. 657-672, 1970
3. Ringel G., Teorema del color del mapa, Springer-Verlag, Berlín 1974
4. Jacques, A. Constellations et propriétés algébriques des graphes topologiques, Ph.D. tesis, París 1969
5. Cori R., Un code pour les graphes planaires et ses applications, Astérisque, vol. 27 de 1975
6. Lienhardt P., Modelos topológicos para la representación de límites: una comparación conmapas generalizados n- dimensionales, Diseño asistido por computadora , Vol. 23, n. ° 1, págs. 59-82, 1991
7. Lienhardt P., mapas combinatorios generalizados N-dimensionales y cuasi-múltiples celulares, Revista internacional de geometría computacional y aplicaciones, vol. 4, no. 3, págs.275-324, 1994

enlaces externos

• Mapas combinatorios en CGAL , la biblioteca de algoritmos de geometría computacional:
  • Damiand, Guillaume. "Mapas combinatorios" . Consultado el 6 de febrero de 2021 .

• Mapas combinatorias en CGoGN , C ombinatorial y G eometric m o Deling con G eneric N -dimensional M aps
• Mapa combinatorio en nLab