Carte combinatoire

Une carte combinatoire est un modèle topologique qui permet de représenter et de manipuler des objets subdivisés. Ce modèle a été tout d'abord définit afin de représenter les graphes planaires. Il a été ensuite étendu pour représenter des objets nD orientables et fermés. Les cartes combinatoires sont utilisées comme une structure de données efficace en traitement d'images ou en modélisation géométrique. Elles ont été également étendues aux cartes généralisées afin de représenter des objets orientables ou non, avec ou sans bord.

Définition

La définition des cartes combinatoires en dimension quelconque est donnée dans ^[1] et ^[2]:

Une carte combinatoire nD (ou n-carte) est un (n + 1)-uplet $C = (B, \beta_1, \dots, \beta_n)$ tel que:

• B est un ensemble fini de brins ;
• β₁ est une permutation sur B ;
• $\beta_2\dots\beta_n$ sont des involutions sur B ;
• $\beta_i \circ \beta_j$ est une involution $\forall i, \forall j, 1 \le i < i + 2 \le j \le n$.

Une carte combinatoire nD représente la subdivision d'un espace nD orientable et fermé. Un brin est un élément abstrait qui est nécessaire à la définition des bijections. La dernière ligne de la définition fixe des contraintes qui garantissent la validité topologique des objets représentés: une carte combinatoire représente une quasi-variété.

Voir aussi

• Plus de détail combinatorial maps(en anglais)
• Boundary representation
• Cartes généralisées
• Simplexe

Références

1. ↑ Lienhardt P., Topological models for Boundary Representation : a comparison with n-dimensional generalized maps, Computer-Aided Design, Vol. 23, no.1, pp. 59-82 - 1991
2. ↑ Lienhardt P., N-dimensional generalized combinatorial maps and cellular quasi-manifolds, International Journal on Computational Geometry and Applications, Vol. 4, n° 3, pp. 275-324 - 1994