Rectilinear Crossing Number

[Heyoka]

Une traduction à faire pour le site de l'AF

http://dist.ist.tugraz.at/cape5//why.html

The Rectilinear Crossing Number Project

Many questions in computational and combinatorial geometry are based on finite sets of points in the Euclidean plane. Several problems from graph theory also fit into this framework, when edges are restricted to be straight. A typical question is the prominent problem of the rectilinear crossing number (related to transport problems and optimization of print layouts for instance): What is the least number of crossings a straight-edge drawing of the complete graph on top of a set of n points in the plane obtains? Here complete graph means that any pair of points is connected by a straight-edge. Moreover we assume general position for the points, i.e., no three points lie on a common line.

It is not hard to see that we can place four points in a way so that no crossing occurs. For five points the drawing shows different ways to place them (these are all different order types (introduced by Goodman and Pollack in 1983)). If you place five points in convex positions then there are five crossings. The best you can do is to get only one crossing (there is no way to draw a complete graph on five points without crossings, even if you allow the edges to be curves). BTW: Maximizing the number of crossings is easy: Just place all n points on a circle to get the maximum of n choose 4 crossings.



For larger point sets it is very hard to determine the best configuration. The main reason is that the number of combinatorially different ways to place those points grows exponentially. For example already for n=11 there are 2,334,512,907 different configurations.

The remarkable hunt for crossing numbers of the complete graph has been initiated by R. Guy in the 1960s. Till the year 2000 only values for n<=9 have been found, in 2001 n=10 was solved and the case n=11 was settled in 2004. The main goal of the current project is to use sophisticated mathematical methods (abstract extension of order types) to determine the rectilinear crossing number for small values of n. So far we have been successful for n <= 17. From very recent (not even published yet) mathematical considerations the rectilinear crossing numbers for n=19 and n=21 are also known. So the most tantalizing problem now is to determine the true value for n=18, which is the main focus of this project.

An updated list for the best point sets known so far can be found at http://www.ist.tugraz.at/staff/aichholzer/crossings.html.

Juli 10, 2006
The RCN-Community is pretty powerful: Only 29 000 WU's are left at the server. Time to insert new ones. The newly inserted (you are likely to get them after 24h) are different in that they are preselected such that no one takes less than 3 seconds. Unfortunately the time consumption for a particular WU is unpredictable. Therefore we do not update the progress bar. Running times of 5 seconds are as normal as running times of 150 hours, however the latter should only occur in rare cases. I set the maximum time for the client's answer to 10 days. The measures will avoid the network overhead we encountered with the xxx-short WU's.

Juli 12, 2006
Another 30 000 workunits inserted. The time consumption is again unpredictable and might be some seconds as well as several days (typically it is some hours). You've been warned. Due to the unpredictable time behavior we can not update the progress bar.

[Heyoka]

Voilà j'ais eu du mal.
Maintenant il faut voire ce qui va pas

Après si on arrive à avoir une belle traduction on peut le soumettre au responsable du projet, il y a dejà une traduction en russe et en allemand.
Et puis aussi je ferais un article sur RCN pour le site de l'AF

Le Projet Rectilinear Crossing Number

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 question les plus récurrentes du volumineux problème des Rectilinear Crossing Number (lié par exemple aux problèmes de transport et à l'optimisation des dispositifs d'impression) : Quel est le nombre minimale d'intersection que l'on pourrait obternir 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 des positions convexes, 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 graphique complet sur cinq points sans croisements, 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 de 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 .