Graphe des segments et la recherche du plus long segment imaginable

Comme nous l'expliquions dans l'introduction, nous nous attardons sur deux cas précis de graphes définissables depuis un arrangement de droites.

Dans le premier cas, celui du graphe des segments, nous allons chercher à trouver la plus grande longueur de chemin telle qu’il existe au moins un arrangement de N droites dont le graphe composé des ~N² intersections ainsi formées possède un chemin d'au moins cette longueur.

Nous appellerons "Lmax(N)" cette longueur, qui est le plus long chemin possible dans un arrangement de N droites. Notre approche ici sera toujours de prouver ou qu'un chemin d'une certaine longueur (Limpossible) n'est pas possible et que donc le chemin le plus long est plus petit (Lmax(N)<Limpossible(N)) ou bien de construire un chemin d'une certaine longueur (Lconnu) et d'en déduire que le chemin le plus long est au moins aussi grand (Lmax(N)>=Lconnu(N)).

Pourquoi chercher le chemin maximal connu?

L’objectif d’une telle valeur serait d'estimer la complexité d'algorithmes se basant sur la recherche d'un chemin dans un arrangement de droite. Souvent, ce type de problème ne possède pas de borne supérieure très précise, et avoir une borne Lconnu(N) permet de se faire une idée de la précision avec laquelle on connaît la complexité du problème (écart entre les bornes inférieures et supérieures possibles).

Borne maximale supérieure du problème

Ce qui est sûr, c’est que vu qu’on a N(N-1) ⁄ 2 sommets à notre graphe, le meilleur cas est un chemin hamiltonien (passant par tous les sommets), et donc de longueur Lhamiltonien = N(N-1) ⁄ 2. Cela nous donne une borne supérieure (Lmax < Lhamiltonien+1).

Borne maximale inférieure du problème

Cas général

Dans le cas qui nous occupe, il n'existe pas de borne inférieure connue au problème qui soit intéressante à mentionner, mais on peut dire qu'à une constante près, il est toujours possible d'atteindre notre borne maximale.

En effet, notre système est très peu contraint, chaque point n'étant pas aux extrémités d'une droite disposant de 4 voisins (les points sur les extrémités en possèdent 2) et ceux-ci sont plutôt variés car deux points ne peuvent jamais avoir plus de deux voisins communs, ce qui laisse une très grande mobilité interne au graphe.

Vu que le nombre de voisins des extrémités est plutôt petit, on imagine qu'il est possible qu'ajouter certains d'entre eux au chemin le plus long pourrait être impossible sous peine de bloquer celui-ci; c'est très peu probable pour les points intérieurs cependant.

Or, le nombre de points à l'extérieur évolue linéairement selon le nombre de droites tandis que le nombre de points total évolue quadratiquement). Au final, on a une progression quadratique du chemin le plus long, et plus N avance, plus le chemin a de chance d'être quasi-hamiltonien.

Cas des espaces projectifs

Cependant, dans certaines conditions, ce problème devient nettement plus simple. En effet, dans un espace projectif (donc un espace dans lequel il est possible de naviguer à travers l'infini et donc de passer d'un bout à l'autre des droites), on se convainc assez facilement que la borne maximale est toujours atteignable dans notre problème.

En effet, tous les points de notre graphe ont au moins quatre connections, vu que désormais on accepte de passer par l’infini pour revenir au début de nos droites. Dans ce cas, pour chaque point, il existe un point avant eux sur la droite ET un point après eux sur la droite, et ce pour les deux droites qui le définissent. Or, on sait que les graphes 4-connectés admettent toujours un chemin hamiltonien, donc un chemin passant par tous les points du graphe. 

Comme aucun chemin ne peut être plus grand qu'un chemin hamiltonien, on a bien trouvé notre borne maximale et notre borne minimale en même temps.

Démonstration (1/1)

Dans cette démonstration, le chemin le plus long (en nombre de points traversés) est calculé. Vous pouvez vous-même ajouter des droites. Comme vous pouvez le constater, ce problème est NP-difficile, cela veut dire qu'il devient exponentiellement plus compliqué quand le nombre de droites augmente. Très vite, votre ordinateur va arriver à saturation. Trouver le chemin le plus long est donc un problème très difficile.

Contrainte de monotonie

Cette fois-ci, nous reprenons le problème précédent, qui était assez facile, mais en rajoutons la contrainte suivante : on ne peut progresser sur une droite que dans une direction donnée, celle dont le produit scalaire avec la "direction monotone" (choisie au préalable) est positif.

Cela rend le problème beaucoup plus compliqué, car on ne peut plus « revenir en arrière » comme on le faisait auparavant. Exemple de chemin interdit :

Chemin le plus long connu

Dans cette configuration, il devient très difficile d'espérer passer par tous les points de l'arrangement. En effet, comment générer un ensemble de points avec des droites, n'autoriser pour chaque segment qu'une seule direction de passage et réussir à relier tous les points? Cela semble irréalisable. On peut cependant s'en rapprocher quand N devient grand, comme le montre la démonstration suivante:

Construction intuitive n°1

Intuitivement, une solution qui parait optimale est trouvée en créant un arrangement en grille, et puis en prenant un chemin en escalier dans cet arrangement. On obtient un chemin de longueur N si on avait N² droites initialement (prenons comme direction monotone (3,2) pour le moment).

Cependant, il est possible de faire mieux. Dans la suite de cet article, nous allons essayer de montrer par quelle méthode les plus longs chemins connus pour ce problème sont actuellement construits.

Construction intuitive n°2

L'idée de base de cette construction est de construire une grille comme la grille précédente puis d'ajouter des "droites de passage" diagonales permettant de relier les points en zigzag, comme on peut le voir ici:

Le problème de cette construction, c'est quelle est difficile à faire grandir quand N devient grand, car les droites de liaison finissent par avoir besoin de pentes telles qu'il n'est plus possible de trouver une direction monotone dans le chemin (nous n'acceptons pas les droites totalement perpendiculaire à la direction monotone).

Le deuxième problème est que le nombre de droites de passage à rajouter devient vite très important et empêche cette construction de prétendre à plus qu'un chemin évoluant linéairement avec le nombre de droites, ce qui n'est au final pas mieux que la méthode précédente.

La technique qui va être utilisée pour résoudre ce problème consiste à trouver une méthode permettant (1) de permettre de s'assurer que toutes les droites à ajouter vont toujours rester penchées dans une direction donnée et (2) de s'assurer que les droites ainsi ajoutées puissent servir plusieurs fois, afin de réduire drastiquement le nombre de droites à ajouter quand N devient grand.

Combinaison des méthodes précédentes

Cette technique, il s'agit de la création d'un graphe fractal. Au lieu de prendre nos "n" droites horizontales et les placer à égale distance des unes des autres, on va prendre une toute petit partie de nos droites (na(0) où a(k) est une suite de "m" nombres dont la somme fait "1") pour former notre grille.

Ensuite, on va remplacer chacune des droites de notre grille par "na(1)" droites très très rapprochées des unes des autres, de telle manière que si on regarde notre problème de loin, on continue à ne voit que "na(0)" droites, même maintenant il y "na(0)*na(1) = n(a(0)+a(1))" droites dessinées. La distance, très courte, entre les droites du deuxième niveau de notre graphe, est appelée ε.

Création d'un arrangement fractal

Comme vous l'aurez deviné, on va continuer ce procédé "m" fois, en remplaçant chacune des droites du niveau 2 par "na(2)" droites très très proches les unes des autres. Pour éviter tout problème, on va prendre une distance les séparant de ε², et ainsi de suite jusqu'à ε^n. Au final, notre grille comptera "2*n(a(0)+a(1)+...a(m-1))" droites, soit "2n" droites, vu que le somme des "m" nombres de "a" est égale à 1 par hypothèse.

Maintenant, il reste à voir comment relier ces points. Tout d'abord, on commence par les niveaux "m", càd les derniers niveaux. Il y a vraiment beaucoup de ces niveaux, et on va donc utiliser l'approche la moins couteuse, càd relier les points de ces "(n1-a(m))²" grilles en utilisant la technique de l'escalier.

Il nous reste alors à relier ces escaliers entre eux. Si l'on remonte d'un niveau, on a l'impression de se retrouver avec une nouvelle grille, où chaque des points a été remplacé par un mini-escalier. On va alors appliquer la deuxième méthode et relier ces mini-escaliers en utilisant la méthode 2, celle qui ajoute des droites intermédiaires.

Enfin, on va faire ceci pour tous les niveaux plus haut et ainsi obtenir une suite de micro-escaliers dans de mini-zigzags dans de petits zigzags ... dans un zigzag. La question est alors de savoir combien de droites on a dû rajouter en suivant ce procédé pour construire le chemin étriqué précédant, en fonction de N.

Comptage du nombre de droites

(1) Compte naïf du nombre de droites et stratégie

Si on veut savoir combien de droites auxiliaires on ajoute, il va falloir compter le nombre de sommets dans les niveaux 1 à m-1 (on n'utilise pas de droites auxiliaires dans le dernier niveau).

Cela fait, pour le niveau "k", le nombre de points à relier est égal au nombre de points du niveau précédent fois le nombre de points par lesquels ceux-ci sont remplacés (n(k) * n(k)) soit "P(k) = P(k-1) * n^(a(k)) * n^(a(k))", soit P(m-1) ~= n² à lui tout-seul. Chacun de ses points a besoin d'une droite, donc le nombre de droites à ajouter "D(k)" est techniquement parlant en O(n²) du nombre de droites de départ, ce qui est beaucoup trop!

Il va donc falloir trouver une manière de pouvoir ajouter bien moins de droites, et cette méthode est de réutiliser les droites qu'on a ajoutée pour de nombreux points.

(2) Comment réutilise-t-on les droites?

Pour se faire, on va choisir des droites ayant des pentes rationnelles (p/q où p et q sont des entiers) de manière à ce que tous les points "n*p" carrés au dessus et "n*q" carrés à gauche du point à partir duquel on la dessine passent également par cette droite. Si ces réutilisations sont massives, on pourrait fortement réduire le nombre de droites ajoutées!

(3) Choix de la direction monotone

La direction monotone choisie dans cette exemple est (√2, 1). La raison de ce choix est que la racine de deux est un nombre irrationnel que l'on va pouvoir approcher par des fractions "p/q" où p et q seront aussi grand que l'on en a besoin.

On sait en effet qu'il existe un chemin monotone entre tous les points de la grille, mais la grille est tellement énorme qu'entre certains points, seules des droites infiniment proches de la perpendiculaire à la direction choisie sont valables, il faut donc pouvoir approcher cette direction aussi précisément que possible avec des fractions, raison pour laquelle il faut une pente irrationnelle.

Plus précisément, il existe une loi qui définit clairement comment approcher au mieux √2 avec une suite de fractions d'une certaine précision au moins "t", et cette loi dit que:

Dans notre cas, la précision nécessaire est le nombre maximum de lignes horizontales que l'on est susceptible de devoir traverser avant d'atteindre notre destination. Il faut en effet que l'on puisse toujours avoir une précision suffisante pour que sur un tel nombre de lignes, la déviation soit insuffisante pour forcer le franchissement d'une ligne verticale de trop ou trop peu.

Ce que nous dit cette formule, c'est que même si on est obligé de respecter cette condition, on peut toujours trouver une approximation "p/q" telle que "q" ne soit jamais plus grand que 10 fois la précision nécessaire, ce qui nous permettra de juger de combien de lignes on va pouvoir réutiliser (en effet, cela dépend de la pente de nos droites, rappelez-vous).

(4) Compte final

Pour le niveau "k", les lignes devront au moins avoir une précision de "n^a(k)" car chaque grille du k-ième niveau possède "n^a(k)" droites horizontales. Cela veut dire que "q <= 10*n^a(k)" selon notre formule d'approximation. On sait aussi que "p <= (√2+δ)q" ou plus simplement "p <= 1.5q" (la pire approximation de racine de deux réalisable vu nos contraintes est 3/2),

Si on prend la grille d'un niveau "k-1", on comprend assez vite que si on construit toutes les droites pour les grilles de niveau "k" des "p" premières lignes et et "p" dernières lignes de notre grille (ou, comme sur la figure qui suit, faire une expérience de la pensée et imaginer les droites sortant de la grille), on va pouvoir couvrir tous les éléments de la grille.

En gros, on a pu utiliser seulement "D(k) = P*(k-2) * [2p * n^a(k-1)] * [n^a(k) * n^a(k)]" droites au lieu de "D(k) = P*(k-1) * [n^a(k-1) * n^a(k-1)] * [n^a(k-1) * n^a(k-1)]". C'est un gros gain, mais ce n'est que la partie visible de l'iceberg.

En effet, si on remonte d'un niveau, on peut à nouveau faire la même constatation: seuls les "p" premiers et "p" derniers points de la grille de niveau "k-3" ont besoin d'avoir une construction de niveau "k-2", ce qui veut dire que, en fait, "D(k) = P*(k-3) * [2p * n^a(k-2)]  * [2p * n^a(k-1)] * [n^a(k) * n^a(k)]" soit en réalité "P(k-2) * (2p)^2 * n^(2a(k)+a(k-1)+a(k-2))".

Si on remonte ainsi jusqu'au niveau 0, on obtient que le nombre de droite à ajouter est en réalité :

Ensuite, on va tenter d'exprimer "p" en fonction de "n", tout d'abord en se rappelant que "p ≤ 1.5q" et donc que "2p ≤ 3q".

Ensuite, on va se rappeler (grâce à [2.6]) que "q(m) <= 10.na(m)":

Ce qui donne finalement (voir choix de "a(k)" et "a(m)"):

Enfin, on n'a tenu compte que des droites "montantes" dans ce calcul, mais on sait que certains points ont besoin de droites descendantes. Pour compenser cela, on peut simplement se dire qu'au pire, chaque point aura besoin des deux (ce n'est bien entendu jamais le cas) et simplement écrire

Résultat final

Vu que "m << n", on a bien ajouté un nombre linéaire de droite, ce qui veut dire qu'on a préservé le coté presque-quadratique de notre progression. Pour être exact:

Une autre manière d'écrire cela, c'est de dire:

Démonstration (1/1)

Dans cette démonstration, le chemin le plus long (en nombre de points traversés) est calculé, avec la contrainte de monotonie: le chemin doit toujours progresser de la gauche vers la droite!

Vous pouvez vous-même ajouter des droites. Comme vous pouvez le constater, ce problème est nettement plus facile, cela veut dire qu'il devient polynomialement plus compliqué quand le nombre de droites augmente. Il va falloit beaucoup de droites pour que votre ordinateur n'arrive à saturation. Trouver le chemin monotone le plus long est donc un problème très facile.

Bibliographie

Cet billet est basé sur l'article "Long Monotone Paths in Line Arrangement" de Jozsef Balogh, Oded Regev, Clifford Smyth, William Steiger et Mario Szegedy paru dans "Discrete & Computational Geometry" (© 2004 Springer-Verlag New York, LLC).