Statut du projet Rectilinear Crossing Number

Le projet Rectilinear Crossing Number vient d'annoncer qu'il reste environ 3,8 millions d'unités W7 à calculer. Une série de calcul W8 devrait également être lancée d'ici à juin 2009 lorsque toutes les unités W7 auront été analysées.

Selon une estimation approximative réalisée par Bernhard Kornberger (l'administrateur du projet Rectilinear), le filtrage interne va devoir encore tourner durant 4 mois supplémentaires. L'épurement réalisé fera diminuer le nombre d'unités W7 et il devrait en rester environ 3,8 millions. Ces unités pourraient toutes être calculées d'ici juin 2009. Ensuite, on enchainera sur le calcul des unités de la série W8.

Il y a quelques mois, Bernhard avait analysé tous les résultats de la série W6 qui venait de se terminer. Suite à cette analyse, les 55 millions d'unités restantes ont été distribuées sous le nom de série W7. 80% de ces unités avaient une durée de fonctionnement extrêmement courte, il a donc été décidé d'effectuer un pré-filtrage : un pré-calcul des 10 premières secondes de chaque unité est ainsi effectué en interne sur plusieurs ordinateurs de l'Université des technologies de Graz. Les unités qui n'ont pas pu être résolues au bout de ces 10 secondes, sont maintenant envoyées aux utilisateurs BOINC via le projet Rectilinear Crossing Number. La plupart de ces unités (environ 90%) vont pouvoir être calculées par les utilisateurs en moins de 2 heures. Toutefois, les unités qui n'auront pas été calculées au bout de ces 2 heures de calcul seront regroupées, puis chacune de ces unités sera segmentée en une centaine d'unités plus petites. Ces nouvelles unités seront rassemblées dans ce que l'on appellera la série de calcul W8.

Ce processus se poursuivra jusqu'à ce qu'il n'y ait plus aucune unité à calculer.

Ce n'est qu'à partir de ce moment que les responsables du projet pourront annoncer le résultat final des calculs. On saura alors comment disposer 20 points dans un graphe complet de telle sorte à minimiser le nombre d'intersections entre les arêtes rectilignes reliant chacun des points du graphe. La conjecture prédit que ce nombre minimal de croisement est compris entre 1652 et 1657.

La découverte du nombre minimal de croisements dans un graphe à 20 points pourrait également permettre d'améliorer la conjecture et ainsi de fixer (ou réduire les encadrements) le nombre minimal de croisements pour des graphes composés de plus de 22 points.

On sait déjà, par exemple, que le nombre minimal de croisement dans un graphe à 21 points est de 2055. Le nombre minimal de croisement dans un graphe à 22 points est compris entre 2521 et 2528. Entre 3075 et 3077 intersections dans un graphe à 23 points, entre 3690  et 3699 intersections dans un graphe à 24 points (les connaissances actuelles sont résumées dans ce tableau).

Ces résultats ont des applications concrètes en matière de transport (optimisation du trafic aérien,...), ou dans les opérations d'impression de documents (photos, images, textes,...).