Recherche des deux points les plus rapprochés

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[1].

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

Algorithmes en dimension 2Modifier

Algorithme naïfModifier

En notant   le nombre de points, l'algorithme naïf par recherche exhaustive a une complexité en temps en  . Il y a en effet   paires différentes à tester.

Algorithme quasi linéaireModifier

Il existe un algorithme basé sur diviser pour régner en  [2].

Description généraleModifier

L'algorithme se déroule en plusieurs étapes[3]:

  1. Préliminaire : créer deux tableaux   et   contenant les   points à étudier. Trier   et   respectivement par abscisses croissantes et par ordonnées croissantes.
  2. Diviser : Si  , trouver une droite verticale qui sépare l'ensemble de points en deux sous-ensembles tels que celui de gauche compte   points et celui de droite  . Sinon faire une recherche exhaustive.
  3. Régner : Résoudre récursivement les deux sous-problèmes obtenus, et récupérer le minimum   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 combinaisonModifier

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 à  . Il suffit donc de s'intéresser à la bande verticale de largeur   centrée en la droite de partition. On procède comme suit[3]:

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

Preuve de validité de l'algorithmeModifier

 
Dans cette configuration, tous les points sont séparés d'une distance  , 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é  . Deux points dans un de ces 8 tiroirs sont séparés de moins de   : on ne peut donc pas placer 9 points séparés de   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é  , ce qui assure qu'aucun appel récursif n'est lancé sur un seul point[3].

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   pour trouver une éventuelle paire de points séparés d'une distance inférieure à  [3]. On suppose qu'il existe pour l'un des sous-problèmes récursifs une paire de points   et   séparés d'une distance inférieure à   (où   est le minimum des distances trouvées dans   et   séparément).   et   sont tous deux compris dans un même rectangle centré sur la droite de partition, de longueur   et de hauteur  .

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  . 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[3]. 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[4]. Par conséquent au plus 7 autres points de la bande ont une ordonnée supérieure de moins de   à l'ordonnée du point  . On peut donc trouver   en calculant au plus 7 distances depuis  . 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  [3].

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

Analyse de complexitéModifier

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

  • L'étape préliminaire de tri a une complexité   (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   premières valeurs de  , c'est-à-dire   opérations.
  • À chaque appel récursif, partage les tableaux   et   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é   à chaque fois[3].
  • L'étape de combinaison des résultats effectue au plus   calculs de distance et a donc une complexité  [3].

La complexité   de l'algorithme vérifie donc la relation de récurrence  . Par conséquent l'arbre des appels récursifs de l'algorithme est un arbre binaire qui comporte   étages, et chaque étage a une complexité  . Ainsi, par le master theorem, l'algorithme est en  [3].

Minoration de la complexitéModifier

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

Optimisation sous certaines hypothèsesModifier

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)[5]. 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[6],[7].

Algorithme en dimension supérieureModifier

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[8].

ApplicationsModifier

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[3].

HistoireModifier

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

Notes et référencesModifier

NotesModifier

référencesModifier

  1. (en) M. I. Shamos et D. Hoey, « Closest-point problems », , 16th Annual Symposium on Foundations of Computer Science, 1975,‎ , p. 151–162 (DOI 10.1109/SFCS.1975.8, lire en ligne, consulté le )
  2. a et b (en) « Computational Geometry - An Introduction | Franco P. Preparata | Springer », sur www.springer.com (consulté le )
  3. a b c d e f g h i j et k Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction à l'algorithmique, Paris, Dunod, , xxix+1146 (ISBN 978-2-10-003922-7, SUDOC 068254024), « Géométrie algorithmique »
  4. a et b (en) Martin Rau et Tobias Nipkow, « Verification of Closest Pair of Points Algorithms », Lecture Notes in Computer Science (en),‎ (lire en ligne), disponible en accès libre.
  5. (en) S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979
  6. (en) S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995
  7. (en) Richard Lipton, « Rabin Flips a Coin »,
  8. (en) Subhash Suri, « Closest Pair Problem », UC Santa Barbara
  9. (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge ; New York, Cambridge University Press (réimpr. 1997, 2000) (1re éd. 1995), 476 p. (ISBN 9780521474658), chap. 9, p. 273