Voir la source de Recherche des deux points les plus rapprochés

[[File:Closest pair of points.svg|thumb|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 algorithmique|problème]] qui consiste à trouver une [[paire]] de [[Point (géométrie)|points]] d'un [[ensemble]] fini de points dans un [[espace métrique]] dont la [[Distance (mathématiques)|distance]] est minimale. Il fait partie des [[Problème algorithmique|problèmes]] fondateurs de la géométrie algorithmique<ref>{{Article|langue=en|prénom1=M. I.|prénom2=D.|nom1=Shamos|nom2=Hoey|titre=Closest-point problems|périodique=, 16th Annual Symposium on Foundations of Computer Science, 1975|date=1975-10-01|doi=10.1109/SFCS.1975.8|lire en ligne=http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=4567872|consulté le=2016-03-25|pages=151–162}}</ref>.

== Algorithmes en dimension 2 ==
=== Algorithme naïf ===
En notant <math>n</math> le nombre de points, l'algorithme naïf par [[recherche exhaustive]] a une [[complexité en temps]] en <math>O(n^2)</math>. Il y a en effet <math>\frac{n(n-1)}{2}</math> paires différentes à tester.

=== Algorithme quasi linéaire ===
Il existe un algorithme basé sur [[Diviser pour régner (informatique)|diviser pour régner]] en <math>O(n \log n)</math><ref name=":0">{{Lien web|langue=en|titre=Computational Geometry - An Introduction {{!}} Franco P. Preparata {{!}} Springer|url=https://www.springer.com/kr/book/9780387961316|site=www.springer.com|consulté le=2016-03-25}}</ref>.

==== Description générale ====
L'algorithme se déroule en plusieurs étapes<ref name="Cormen"/>:
# '''Préliminaire''' : créer deux [[Tableau (structure de données)|tableaux]] <math>T_x</math> et <math>T_y</math> contenant les <math>n</math> points à étudier. [[Algorithme de tri|Trier]] <math>T_x</math> et <math>T_y</math> respectivement par [[abscisse]]s croissantes et par [[ordonnée]]s croissantes.
# '''Diviser''' : Si <math>n > 3</math>, trouver une droite verticale qui sépare l'ensemble de points en deux sous-ensembles tels que celui de gauche compte <math>\left\lfloor{\frac{n}{2}}\right\rfloor</math> points et celui de droite <math>n - \left\lfloor{\frac{n}{2}}\right\rfloor</math>. Sinon faire une recherche exhaustive.
# '''Régner''' : Résoudre [[Récursivité|récursivement]] les deux sous-problèmes obtenus, et récupérer le minimum <math>\delta</math> des deux solutions.
# '''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'[[Instruction informatique|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 à <math>\delta</math>. Il suffit donc de s'intéresser à la bande verticale de largeur <math>2\delta</math> centrée en la droite de partition. On procède comme suit<ref name="Cormen"/>:

# Créer un tableau <math>T'_y</math> ne contenant que les points de <math>T_y</math> compris dans la bande considérée triés selon les ordonnées croissantes.
# Pour chaque point <math>P</math> de la bande, calculer la distance qui sépare <math>P</math> aux {{formatnum:7}} points qui le suivent dans le tableau <math>T'_y</math> et noter le minimum <math>\delta'</math> de toutes les distances obtenues.
# Si <math>\delta' < \delta</math> renvoyer <math>\delta'</math> sinon renvoyer <math>\delta</math>.

==== Preuve de validité de l'algorithme ====
[[File:Plus-proche-cormen.png|thumb|left|Dans cette configuration, tous les points sont séparés d'une distance <math>\delta</math>, 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.]]
[[File:Plus-proche-tiroir.png|thumb|right|Le grand rectangle est découpé en 8 carrés de côté <math>\frac{\delta}{2}</math>. Deux points dans un de ces 8 [[principe des tiroirs|tiroirs]] sont séparés de moins de <math>\delta</math> : on ne peut donc pas placer 9 points séparés de <math>\delta</math> dans le grand rectangle.]]
La [[Terminaison d'un algorithme|terminaison]] de l'algorithme est assurée par le fait que l'on a choisi pour limite de récursivité  <math>n \leq 3</math>, ce qui assure qu'aucun appel récursif n'est lancé sur un seul point<ref name="Cormen"/>.

Le point le plus important à vérifier pour établir la [[Correction (logique)|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 <math>T'_y</math> pour trouver une éventuelle paire de points séparés d'une distance inférieure à <math>\delta</math><ref name="Cormen"/>.
On suppose qu'il existe pour l'un des sous-problèmes récursifs une paire de points <math>P \in \mathtt{Gauche}</math> et <math>P'\in \mathtt{Droite}</math> séparés d'une distance inférieure à <math>\delta</math> (où <math>\delta</math> est le minimum des distances trouvées dans <math>\mathtt{Gauche}</math> et <math>\mathtt{Droite}</math> séparément). <math>P</math> et <math>P'</math> sont tous deux compris dans un même rectangle centré sur la droite de partition, de longueur <math>2\delta</math> et de hauteur <math>\delta</math>.

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 <math>\delta</math>. La réponse est {{formatnum:8}} : un à chaque coin, et un couple de points superposés situé à chacun des milieux des grands côtés du rectangle<ref name="Cormen"/>. Cet argument repose sur l'intuition géométrique et n'est pas adapté à une [[Méthode formelle (informatique)|formalisation]] rigoureuse, mais peut être remplacé par une utilisation du [[principe des tiroirs]] qui donne la même borne de manière rigoureuse<ref name="rau">{{Article|langue = anglais|titre =Verification of Closest Pair of Points Algorithms|périodique = {{Lien| trad = Lecture Notes in Computer Science}} |date = 24 juin 2020|auteur1= Martin Rau|auteur2 = Tobias Nipkow|lire en ligne =https://link.springer.com/chapter/10.1007/978-3-030-51054-1_20}}, disponible en accès libre.</ref>. Par conséquent au plus {{formatnum:7}} autres points de la bande ont une ordonnée supérieure de moins de <math>\delta</math> à l'ordonnée du point <math>P</math>. On peut donc trouver <math>P'</math> en calculant au plus {{formatnum:7}} distances depuis <math>P</math>. 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 {{formatnum:7}} points qui le suivent dans <math>T'_y</math><ref name="Cormen"/>.

La validité du reste de l'algorithme ne nécessite pas de preuve détaillée<ref name="Cormen"/>, celle-ci a néanmoins été vérifiée formellement dans son intégralité à l'aide de l'[[assistant de preuve]] [[Isabelle (logiciel)|Isabelle]]<ref name="rau"/>.

==== 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é <math>O(n \log n)</math> (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 <math>\left\lfloor{\frac{n}{2}}\right\rfloor</math> premières valeurs de <math>T_x</math>, c'est-à-dire <math>O(n)</math> opérations.

* À chaque appel récursif, partage les tableaux <math>T_x</math> et <math>T_y</math> 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é <math>O(n)</math> à chaque fois<ref name="Cormen"/>.

* L'étape de combinaison des résultats effectue au plus <math>7n</math> calculs de distance et a donc une complexité <math>O(n)</math><ref name="Cormen"/>.

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

=== 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<ref name=":0" />.

=== Optimisation sous certaines hypothèses ===
Si on suppose que la fonction [[Partie entière et partie fractionnaire|partie entière]] est calculable en temps constant, alors le problème se résout en {{nowrap|O(''n'' log log ''n'')}}<ref name=fh>{{en}} S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979</ref>.
Si on s'autorise des [[algorithme probabiliste|algorithmes probabilistes]] (et la fonction partie entière calculable en temps constant), alors le problème se résout en {{nowrap|O(''n'')}} en [[Espérance mathématique|espérance]]<ref name=km>{{en}} S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995</ref>[[Espérance mathématique|{{,}}]]<ref name=rl>{{lien web|langue=en|url=http://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/ |titre=Rabin Flips a Coin |auteur= Richard Lipton|date=24 septembre 2011}}</ref>.

== Algorithme en dimension supérieure ==

L'algorithme diviser pour régner se généralise à toute [[dimension d'un espace vectoriel|dimension]] ''d'', avec une complexité de O(''n'' log ''n'') à dimension fixée, mais avec une dépendance exponentielle en la dimension<ref>{{Lien web|langue=en|url=https://sites.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf|titre=Closest Pair Problem|nom=Suri|prénom=Subhash|date=|website=|éditeur=UC Santa Barbara}}</ref>.

== 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 à {{formatnum:3}} dimensions), et ainsi prévenir le risque de collision<ref name="Cormen">{{Ouvrage | auteur1=[[Thomas H. Cormen]] | auteur2=[[Charles E. Leiserson]] | auteur3=[[Ronald L. Rivest]] | titre=[[Introduction à l'algorithmique]] | lieu=Paris | éditeur=[[Éditions Dunod|Dunod]] | année=2002 | pages totales=xxix+1146 | isbn=978-2-10-003922-7 | sudoc=068254024 | titre chapitre=Géométrie algorithmique}}
</ref>.

== Histoire ==
L'algorithme de [[Michael O. Rabin]] pour ce problème est l'un des premiers algorithmes géométriques probabilistes<ref>
{{Randomized Algorithms (Motwani et Raghavan)
 |passage = 273
 |chapitre= Geometric Algorithms and Linear Programming
 | numéro chapitre = 9
}}
</ref>.

== Notes et références ==
=== Notes ===
{{Références|group=Note}}

=== références ===
{{Références}}

{{Portail|géométrie|informatique théorique}}

[[Catégorie:Problème algorithmique]]