Suite à une attaque du serveur du projet par des hackers, les responsables de la recherche ont décidé de terminer les calculs en interne.
Par chance, aucune donnée n'a été perdue suite à cet acte malveillant, cependant l'équipe scientifique ne dispose pas des moyens humains et financiers pour reconfigurer le serveur et résoudre les failles de sécurité.
La fin du projet est suffisamment proche pour que les derniers calculs soient effectués dans un délai raisonnable sur le réseau informatique de l'université de Graz en Autriche.
L'équipe du projet tiendra la communauté au courant des progrès des calculs effectués en interne.
URL du projet : http://dist.ist.tugraz.at/cape5/
Etude sur la façon de placer 20 points dans un graphe complet tout en minimisant le nombre d'intersections
Débouchés possibles dans des problèmes actuels en matière de transport (optimisation du trafic aérien,...), ou dans les opérations d'impression de documents (photos, images, textes,...)
- Résultats (placer 18 points dans un graphe complet) - Article de Futura-Sciences
Le Projet Rectilinear Crossing Number
De nombreux problèmes de géométrie algorithmique et combinatoire ont pour point de départ un ensemble fini 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 (les segments de droite qui relient les points) sont rectilignes. L'une des questions les plus récurrentes du volumineux problème des nombres de croisement rectilignes ou "Rectilinear Crossing Number" est la suivante : Quel est le nombre minimal d'intersections que l'on pourrait obtenir en traçant des segments de droites sur un graphe complet reliant un ensemble de n points différents ? Ici le graphe complet exige que tous les points soient reliés deux à deux par un segment de droite. L'hypothèse de départ est que trois points ne peuvent se retrouver sur le même segment de droite. Cet problème peut par exemple trouver des débouchés dans le domaine des transports ou l'optimisation des opérations d'impression.
On peut facilement comprendre qu'il est possible de placer quatre points de sorte qu'aucun croisement ne se produise. Le schéma ci-dessous montre les différentes solutions possibles pour placer 5 points. 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 tracez des lignes non rectilignes. 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 nombres rectilignes 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ées), on connait le nombres de croisement rectilignes 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)
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/ .
L'écran de veille
Notez que par soucis de simplification, l'écran de veille représente uniquement la structure générale du graphe et non pas tout les segments reliant chacun des points du graphe.
