Recherche des deux points les plus rapprochés

Une paire de points les plus proches (en rouge).

En géométrie algorithmique, la recherche des deux points les plus rapprochés est le problème qui consiste à trouver une paire de points d'un ensemble fini de points dans un espace métrique dont la distance est minimale. Il fait partie des problèmes fondateurs de la géométrie algorithmique.

Algorithmes en dimension 2

Algorithme naïf

En notant $n$ le nombre de points, l'algorithme naïf par recherche exhaustive a une complexité en temps en $O(n^{2})$. Il y a en effet ${\frac {n(n-1)}{2}}$ paires différentes à tester.

Algorithme quasi linéaire

Il existe un algorithme basé sur diviser pour régner en $O(n\log n)$.

Description générale

L'algorithme se déroule en plusieurs étapes:

1. Préliminaire : créer deux tableaux $T_{x}$ et $T_{y}$ contenant les $n$ points à étudier. Trier $T_{x}$ et $T_{y}$ respectivement par abscisses croissantes et par ordonnées croissantes.
2. Diviser : Si $n>3$, trouver une droite verticale qui sépare l'ensemble de points en deux sous-ensembles tels que celui de gauche compte $\left\lfloor {\frac {n}{2}}\right\rfloor$ points et celui de droite $n-\left\lfloor {\frac {n}{2}}\right\rfloor$. Sinon faire une recherche exhaustive.
3. Régner : Résoudre récursivement les deux sous-problèmes obtenus, et récupérer le minimum $\delta$ des deux solutions.
4. Combiner : Comparer le minimum obtenu dans la résolution des deux sous-problèmes, ainsi que le minimum obtenu pour des paires dont chaque extrémité est issue d'un sous-problème distinct. C'est l'étape qui nécessite le plus d'instructions.

Détail de l'étape de combinaison

La résolution des deux sous-problèmes permet de déterminer que si la paire de points les plus proches a une extrémité de chaque côté de la droite de partition, alors la distance qui les sépare est inférieure à $\delta$. Il suffit donc de s'intéresser à la bande verticale de largeur $2\delta$ centrée en la droite de partition. On procède comme suit:

1. Créer un tableau $T'_{y}$ ne contenant que les points de $T_{y}$ compris dans la bande considérée triés selon les ordonnées croissantes.
2. Pour chaque point $P$ de la bande, calculer la distance qui sépare $P$ aux 7 points qui le suivent dans le tableau $T'_{y}$ et noter le minimum $\delta '$ de toutes les distances obtenues.
3. Si $\delta '<\delta$ renvoyer $\delta '$ sinon renvoyer $\delta$.

Preuve de validité de l'algorithme

Dans cette configuration, tous les points sont séparés d'une distance $\delta$, et il y en a 8 en considérant que les points sur la droite frontière sont dédoublés et comptés l'un à gauche et l'autre à droite. Il n'est pas possible de rajouter un neuvième point dans cette configuration.

Le grand rectangle est découpé en 8 carrés de côté ${\frac {\delta }{2}}$. Deux points dans un de ces 8 tiroirs sont séparés de moins de $\delta$ : on ne peut donc pas placer 9 points séparés de $\delta$ dans le grand rectangle.

La terminaison de l'algorithme est assurée par le fait que l'on a choisi pour limite de récursivité $n\leq 3$, ce qui assure qu'aucun appel récursif n'est lancé sur un seul point.

Le point le plus important à vérifier pour établir la correction de l'algorithme est le fait que dans l'étape de combinaison des résultats des sous-problèmes, il suffit de calculer la distance entre chaque point et les sept suivants dans $T'_{y}$ pour trouver une éventuelle paire de points séparés d'une distance inférieure à $\delta$. On suppose qu'il existe pour l'un des sous-problèmes récursifs une paire de points $P\in {\mathtt {Gauche}}$ et $P'\in {\mathtt {Droite}}$ séparés d'une distance inférieure à $\delta$ (où $\delta$ est le minimum des distances trouvées dans ${\mathtt {Gauche}}$ et ${\mathtt {Droite}}$ séparément). $P$ et $P'$ sont tous deux compris dans un même rectangle centré sur la droite de partition, de longueur $2\delta$ et de hauteur $\delta$.

On cherche à savoir combien de points au maximum peuvent se trouver dans ce rectangle, sachant que deux points situés du même côté de la droite de partition sont distants d'au moins $\delta$. La réponse est 8 : un à chaque coin, et un couple de points superposés situé à chacun des milieux des grands côtés du rectangle. Cet argument repose sur l'intuition géométrique et n'est pas adapté à une formalisation rigoureuse, mais peut être remplacé par une utilisation du principe des tiroirs qui donne la même borne de manière rigoureuse. Par conséquent au plus 7 autres points de la bande ont une ordonnée supérieure de moins de $\delta$ à l'ordonnée du point $P$. On peut donc trouver $P'$ en calculant au plus 7 distances depuis $P$. On peut donc trouver une paire minimale si elle existe au sein de la bande en calculant pour chacun de ses points les distances qui le séparent des 7 points qui le suivent dans $T'_{y}$.

La validité du reste de l'algorithme ne nécessite pas de preuve détaillée, celle-ci a néanmoins été vérifiée formellement dans son intégralité à l'aide de l'assistant de preuve Isabelle.

Analyse de complexité

On commence par regarder la complexité des différentes étapes de l'algorithme :

• L'étape préliminaire de tri a une complexité $O(n\log n)$ (en utilisant par exemple le tri fusion) et n'est exécutée que deux fois.

• La partition de l'ensemble de points par une droite verticale nécessite le parcours des $\left\lfloor {\frac {n}{2}}\right\rfloor$ premières valeurs de $T_{x}$, c'est-à-dire $O(n)$ opérations.

• À chaque appel récursif, partage les tableaux $T_{x}$ et $T_{y}$ en deux sous-tableaux ne contenant que les points des sous-ensembles considérés. Cette découpe peut être effectuée avec une complexité $O(n)$ à chaque fois.

• L'étape de combinaison des résultats effectue au plus $7n$ calculs de distance et a donc une complexité $O(n)$.

La complexité ${\mathcal {C}}(n)$ de l'algorithme vérifie donc la relation de récurrence ${\mathcal {C}}(n)=2{\mathcal {C}}\left({\frac {n}{2}}\right) O(n)$. Par conséquent l'arbre des appels récursifs de l'algorithme est un arbre binaire qui comporte $\log n$ étages, et chaque étage a une complexité $O(n)$. Ainsi, par le master theorem, l'algorithme est en $O(n\log n)$.

Minoration de la complexité

On sait aussi que tout algorithme nécessite Ω(n log n) étapes de calcul pour trouver deux points les plus rapprochés.

Optimisation sous certaines hypothèses

Si on suppose que la fonction partie entière est calculable en temps constant, alors le problème se résout en O(n log log n). Si on s'autorise des algorithmes probabilistes (et la fonction partie entière calculable en temps constant), alors le problème se résout en O(n) en espérance.

Algorithme en dimension supérieure

L'algorithme diviser pour régner se généralise à toute dimension d, avec une complexité de O(n log n) à dimension fixée, mais avec une dépendance exponentielle en la dimension.

Applications

Ce problème de recherche est utilisé par les contrôleurs aériens pour repérer les avions les plus proches les uns des autres (l'espace considéré est ici à 3 dimensions), et ainsi prévenir le risque de collision.

Histoire

L'algorithme de Michael O. Rabin pour ce problème est l'un des premiers algorithmes géométriques probabilistes.