Stage de recherche UM2 proposé par E. Gioan

Proposition de stage de recherche, Université Montpellier 2, année 2011-2012

Implications entre orientations de triangles ou de tétraèdres

Encadrant : Emeric Gioan (LIRMM, équipe AlGCo : Algorithmes, Graphes et Combinatoire)
Prérequis : algorithmique, combinatoire, et si possible un peu d'algèbre linéaire et de géométrie 2D/3D
Résumé. On appelle chirotope l'orientation (c'est un signe + ou -) d'un triangle (en 2D) ou d'un tétraèdre (en 3D). L'ensemble des chirotopes d'un ensemble donné de points satisfait des règles algébrico/combinatoires connues. Ici, on connait une partie A de l'ensemble des chirotopes. On cherche à calculer algorithmiquement quel sous-ensemble plus grand est impliqué par cet ensemble A, en suivant les règles, ainsi qu'un sous-ensemble plus petit qui impliquerait l'ensemble A.

Présentation détaillée du sujet.

Soit un ensemble fini E (appelé ensemble des points, par exemple E=1,2,3,4,...,n) et un entier d (appelé la dimension).
A chaque (d+1)-uplet de points e₁,...,e_d+1 est associé un signe + ou -, que l'on appelle chirotope et que l'on note [e₁...e_d+1].
On s'intéressera a priori aux dimensions d=2 et d=3 (mais les énoncés qui suivent peuvent être généralisés à d quelconque).

Exemples géométriques et algébriques
Les chirotopes qui nous intéressent viennent des situations géométriques suivantes.
Ces exemples peuvent aider l'intuition et sont ceux dans lesquels nous aurons des applications, mais le problème peut se poser sans utiliser de géométrie ou d'algèbre linéaire.

En 2D
E est un ensemble de points dans le plan affine en position générale (il n'y a pas 3 points alignés).
Le chirotope [abc] est donné par l'orientation du triangle abc, parcouru dans le sens a puis b puis c.
On choisit arbitrairement un sens + et un sens -, usuellement dans le sens trigonométrique on donne le signe +, dans le sens des aiguilles d'une montre on donne le signe -.
Bien sûr, ce signe s'obtient également comme déterminant de la matrice 3*3 dont les colonnes sont les coordonnées des points dans le plan, avec un 1 en première ligne.
En 3D
E est un ensemble de points dans l'espace affine en position générale (il n'y a pas 4 points coplanaires).
Le chirotope [abcd] est donné par l'orientation du tétraèdre abcd, parcouru dans le sens a puis b puis c puis d.
Ce signe s'obtient également comme déterminant de la matrice 4*4 dont les colonnes sont les coordonnées des points dans l'espace, avec un 1 en première ligne.

Propriétés
Les chirotopes satisfont les règles suivantes.

Alternance
Pour toute permutation s, on a [e_s(1)...e_s(d+1)]=signe(s).[e₁...e_d+1]
Par exemple échanger la place de deux points change le signe : [123]= - [213]=[231]= - [321]
Consistence
- En 2D
  pour tout x,a,b,c,d dans E les 3 signes suivants ne peuvent pas être tous égaux
  [xab].[xcd]
  - [xac].[xbd]
  [xad].[xbc]
  (un signe par ligne, chacun est le produit de deux chirotpes)
- En 3D
  pour tout x,y,a,b,c,d dans E les 3 signes suivants ne peuvent pas être tous égaux
  [xyab].[xycd]
  - [xyac].[xybd]
  [xyad].[xybc]
  (un signe par ligne, chacun est le produit de deux chirotpes)

Acyclicité
- En 2D
  pour tout a,b,c,d dans E les 4 signes suivants ne peuvent pas être tous égaux
  [bcd]
  -[acd]
  [abd]
  -[abc]
  (un signe par ligne)
- En 3D
  pour tout a,b,c,d,e les 5 signes suivants ne peuvent pas être tous égaux
  [bcde]
  -[acde]
  [abde]
  -[abce]
  [bcde]
  (un signe par ligne)

Contexte théorique
Les propriétés ci-dessus viennent de la théorie des matroïdes orientés [1][2], qu'il n'est pas indispensable de connaître ou d'étudier pour aborder ce stage.
En général, les chirotopes sont un signe associé aux bases d'un matroïde, lui conférant une structure de matroïde orienté.
La règle de consistence assure que le matroide orienté est structurellement bien défini, et la règle d'acyclicité indique, s'il s'agit de points géométriques, que ces points sont représentables dans un espace affine de dimension d (et non pas seulement dans un espace vectoriel de dimension d+1).
En fait les chirotopes peuvent admettre en général un signe 0 (points alignés par exemple), mais ici nous nous restreignons au cas uniforme, sans signe 0.

Dans ce stage, on va s'intéresser à des chirotopes partiellement définis, que l'on va chercher à compléter ou à réduire.

Pour information, signalons en passant les résultats algorithmiques suivants (qui dépassent le cadre de ce stage) :
- Tester si une application partiellement définie peut-etre complétée en un chirotope (i.e. satisfaisant les propriétés ci-dessus) est un problème NP-complet [3]. Ici nous supposerons toujours que la définaition partielle que nous avons est bien la définition partielle d'un chirotope.
- Tester si un ensemble de bases peut-être signé ainsi est un problème NP-complet [4]. Ici nous nous concentrerons sur le cas uniforme pour lequel on peut toujours trouver de tels signes.

Travail principal du stage
On suppose que l'on connait les valeurs des chirotopes pour un ensemble A de triplets (en 2D) ou de quadruplets (en 3D) de points de E.

Les règles énoncées ci-dessus pour les chirotopes peuvent imposer les valeurs des chirotopes d'éléments n'appartenant pas à A.
Etablir un algorithme qui calcule toutes ces valeurs, c'est à dire le plus petit ensemble fc(A) contenant A dont les chirotopes sont impliqués par ceux de A.

Toujours grace aux propriétés ci-dessus, certaines valeurs de chirotopes d'éléments de A peuvent être impliquées par d'autres valeurs dans A, elles peuvent être enlevées de A sans changer l'ensemble engendré.
Etablir un algorithme qui calcule un nombre maximal de telles valeurs, c'est à dire un ensemble A' minimal contenu dans A tel que fc(A')=fc(A).

Chaque fois évaluer la complexité de l'algorithme et chercher à l'améliorer.

Travaux annexes potentiels (selon les avancées et motivations du stagiaire)

Programmer les algorithmes en C (les programmes seront intégrés à un logiciel actuellement en développement)
Programmer les caractérisations en Haskell (programmation fonctionnelle)
Trouver des cas particuliers intéressants (par exemple peu d'éléments qui en engendrent beaucoup)
Si besoin est, proposer des heuristiques pour trouver rapidement un ensemble A' proche d'un ensemble optimal
Approfondir les propriétés structurelles utilisées dans les algorithmes
Aborder le problème en termes de théorie des matroïdes orientés (l'encadrant en est spécialiste)
Etudier la fonction fc (c'est la grande question fondamentale sous-jacente), notamment comment se caractérisent et s'ordonnent les ensembles fc(A) pour différents ensembles A
Si on ne suppose plus que l'application partielle peut-être complétée en un chirotope, détecter si c'est le cas, et sinon comment transformer l'application pour que ce soit le cas (problème NP-complet en général, mais nous sommes intéressés ici par des application définies partiellement sur un petit sous-ensemble)
Le stagiaire sera libre de proposer et d'étudier d'autres approfondissements du sujet...

Intérêt
Ces recherches ont un intérêt fondamental pour la compréhension des positions relatives de triangles/tétraèdres, et plus généralement pour l'axiomatique des matroïdes orientés.
De plus ils s'intègrent à un projet de recherche mené actuellement au LIRMM (Gioan, Sol, Subsol) consistant à étudier des modèles 3D issus de l'anthropologie au moyen de ces orientations.
On est amené à considérer des ensembles de tétraèdres dont l'orientation est fixée, détectée par des critères de classification ou imposée par des critères morphologiques [5].
Les algorithmes à trouver dans ce stage ont pour but d'étendre ou de réduire ces ensembles le plus possible, afin d'étudier au mieux leurs propriétés et celles des critères employés.

Références :

[1] Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). Oriented Matroids. Cambridge University Press.

[2] Richter-Gebert, J. and G. Ziegler, Oriented Matroids, In Handbook of Discrete and Computational Geometry, J. Goodman and J.O'Rourke, (eds.), CRC Press, Boca Raton, 1997, p. 111-132.

[3] Falk Tschirschnitz. Testing Extendability for Partial Chirotopes is NP-Complete. PROCEEDINGS OF THE 13TH CANADIAN CONFERENCE ON COMPUTATIONAL GEOMETRY (2001)

[4] J. Richter-Gebert: “Orientability of matroids is NP-complete”. Advances in Applied Mathematics (special issue: “in the honor of Henry Crapo” , ed. J. Kung), 23 (1999) 78–90.

[5] Emeric Gioan, Kevin Sol et Gérard Subsol. Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices. Proceedings CCCG'2011, 6p. (2011).