Carte combinatoire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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éfini 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[modifier | modifier le code]

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 ;
  • \beta_1 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[modifier | modifier le code]

Références[modifier | modifier le code]

  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

Liens externes[modifier | modifier le code]