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. 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. Il existe un algorithme basé sur diviser pour régner en . L'algorithme se déroule en plusieurs étapes: Préliminaire : créer deux tableaux et contenant les points à étudier. Trier et respectivement par abscisses croissantes et par ordonnées croissantes. 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. Régner : Résoudre récursivement les deux sous-problèmes obtenus, et récupérer le minimum 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'instructions. 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: Créer un tableau ne contenant que les points de compris dans la bande considérée triés selon les ordonnées croissantes. Pour chaque point de la bande, calculer la distance qui sépare aux points qui le suivent dans le tableau et noter le minimum de toutes les distances obtenues. Si renvoyer sinon renvoyer . 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.