Recherche des deux points les plus rapprochés

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Une paire de points les plus proches (en rouge)

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

Problème algorithmique[modifier | modifier le code]

Étant donné un ensemble de points dans un espace métrique, le problème consiste à trouver une paire de points séparés par une distance minimale.

C'est l'un des problèmes importants de la géométrie algorithmique[1].

Algorithmes en dimension 2[modifier | modifier le code]

Algorithme naïf[modifier | modifier le code]

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éaire[modifier | modifier le code]

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

Description générale[modifier | modifier le code]

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 combinaison[modifier | modifier le code]

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és 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'algorithme[modifier | modifier le code]

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

Analyse de complexité[modifier | modifier le code]

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'algorithme est en [3],[4].

Minoration de la complexité[modifier | modifier le code]

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èses[modifier | modifier le code]

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

Applications[modifier | modifier le code]

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

Histoire[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. 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)
  2. a et b « Computational Geometry - An Introduction | Franco P. Preparata | Springer », sur www.springer.com (consulté le 25 mars 2016)
  3. a, b, c, d, e, f, g, h, i, j et k (en) Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction à l'algorithmique, Paris, Dunod, , xxix+1146 p. (ISBN 978-2100-03922-7, SUDOC 068254024), « Géométrie algorithmique »
  4. Cela peut se justifier par le master theorem ou en considérant l'arbre des appels récursifs de l'algorithme : celui-ci comporte étages, et chaque étage a une complexité .
  5. S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979
  6. 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) 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