Boinc - Equipe de la Science

Beaucoup de questions de la 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, quand 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 minimale d'intersection 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 dans de manière convexe, on observe cinq croisements. Le mieux que vous puissiez faire est d'obtenir seulement une intersection (il n'y a aucune 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. C'est pourquoi le travail le plus captivant est actuellement de déterminer la valeur correcte pour n=18, ce qui est le but principal de ce projet.

Une liste (constament mise à jour) des meilleurs ensembles de point connus jusqu'ici est consultable à cette addresse :

http://www.ist.tugraz.at/staff/aichholzer/crossings.html