Rectilinear Crossing Number

[sbmtl]

Projet basé en Autriche.

Ce projet a des implications dans le domaine aéronautique et le domaine de l'impression.

Le Projet Rectilinear Crossing Number*

Beaucoup de questions en géométrie informatique et combinatoire se basent sur un ensemble finis de points dans un espace euclidien. Plusieurs problèmes de la théorie des graphes sont également adaptés à ce cadre, par exemple lorsque les arêtes sont définis par avance par une ligne droite. Une des questions les plus récurrentes du volumineux problème des Rectilinear Crossing Number (lié par exemple aux problèmes de transport et à l'optimisation des opérations d'impression) : Quel est le nombre minimal d'intersections que l'on pourrait obtenir en traçant des lignes droites sur un graphe complet reliant un ensemble de n points différents ? Ici le graphe complet signifie que n'importe quelle paire de points est reliée par une ligne droite. L'hypothèse de départ est que trois points ne peuvent se retrouver sur la même arrête.

On peut facilement voire qu'il est possible de placer quatre points de sorte qu'aucun croisement ne se produise. Pour cinq points le schéma ci-dessous montre les différentes manières de les placer (Voilà la totalité des différents types d'ordre (présentés par Goodman et Pollack en 1983)). Lorsque l'on dispose cinq points de façon convexe dans un graphe, on observe cinq croisements. Le mieux que vous puissiez faire est d'obtenir seulement une intersection (il n'y a aucune autre manière de tracer un graphe complet de cinq points sans croisement, sauf si vous permettez des arêtes courbées). De la même manière, il est facile de maximiser le nombre de croisements : il suffit simplement de placer les n points sur un cercle pour obtenir le maximum de croisements (n supérieur à 4)



Pour de plus grands ensembles de point, il est plus difficile de déterminer la meilleure configuration. La raison principale est que le nombre de combinaisons différentes pour placer ces points augmente exponentiellement. Par exemple, il y a dejà 2.334.512.907 possibilités différentes pour n=11 points

La "chasse" aux Crossing Number dans un graphe complet a été ouverte par R. Guy dans les années 60. Jusqu'en 2000, des valeurs pour n<=9 ont été trouvé, en 2001 n=10 a été résolu et le cas de n=11 a été terminé en 2004. Le but principal du projet en cours est d'employer des méthodes mathématiques sophistiquées (prolongement abstrait des types d'ordre) pour déterminer le nombre d'intersections linéaires pour de petites valeurs de n. Jusqu'ici nous avons accomplis avec succès ce travail pour n <= 17 . Grâce à des recherches mathématiques très récentes (non encore publié), on connait les rectilinear crossing numbers pour n=19 et n=21.

En Janvier 2007, le nombre minimal d'intersection pour n=18 a été trouvé ; CR(18)=1029 (voir les résultats)
https://afquebec.forum-canada.net/post.forum?mode=editpost&p=169
C'est pourquoi le travail le plus captivant est actuellement de déterminer la valeur correcte pour n=20.

Une liste (régulièrement mise à jour) des meilleurs ensembles de points connus jusqu'ici est consultable à cette addresse :

http://www.ist.tugraz.at/staff/aichholzer/research/rp/triangulations/crossing/ .

*Informations tirées du site de L'Alliance Francophone: http://www.boinc-af.org/

Autres articles sur le projet:
http://www.futura-sciences.com/fr/news/t/recherche/d/boinc-et-theorie-des-graphes-une-nouvelle-performance_10368/

Site du projet
Joindre l'Alliance Francophone sur le projet
État des serveurs
Notre position sur le projet