Deux points les plus proches

Page Wikipedia

On donne un tableau de points du plan avec leurs coordonnées $(x\,;\,y)$.

Quels sont les deux points les plus proches ?

Consiste à chercher les distances pour les $\frac{n\,(n-1)}{2}$ paires de points possibles. Il s'agit donc d'un algorithme en $n^2$, c'est à dire que s'il y a $10\times$ plus de points, l'algorithme sera $100\times$ plus long.

Quasi-linéaire signifie que s'il y a $10\times$ plus de points, le temps de calcul sera quasiment $10\times$ plus long. On comprend que cet algorithme devient beaucoup plus rapide quand le nombre de points augmente. Il faut bien sûr considérer de très grands nombres, par exemple 100 000. Tant qu'il n'y a qu'une centaine de points, la machine calcule très vite sans qu'on perçoive de différence.

Il s'agit d'un algorithme de type diviser pour régner.

On réalise une fonction recherche qui reçoit en argument une liste points de paires (x,y).

Si le nombre n de paires est inférieur ou égal à 3, on se contente de faire une recherche exhaustive de la paire la plus proche.

Sinon on lance le mécanisme habituel de la méthode diviser pour régner qui procède en 3 étapes :

Déterminer une abscisse $x_0$ permettant de couper la liste de points en deux. Ceux à gauche et ceux à droite de $x_0$. On forme ainsi deux ensembles de points que l'on peut appeler $G$ et $D$.

On exécute recherche sur les deux sous ensembles, $G$ et $D$. On obtient ainsi la paire de points les plus proches dans $G$ et la paire de points les plus proches dans $D$.

C'est le plus compliqué :

• L'étape précédente à produit deux réponses. On sélectionne celle qui donne la distance la plus courte. Notons $\delta$ cette distance. C'est la distance entre deux points de $G$ ou de $D$.
• Nous devons chercher s'il n'y aurait pas une paire de points, l'un dans $G$ et l'autre dans $D$, dont la distance serait plus petite. Pour cela on procède à une nouvelle recherche en procédant ainsi :
  • On sélectionne dans $G$ les points dont l'abscisse est dans $[x_0-\delta\,;\,x_0]$ et dans $D$ ceux dont l'abscisse est dans $[x_0\,;\,x_0+\delta]$. On forme ainsi un ensemble $B$.
  • On parcours les points de $B$ par ordonnées croissantes. Pour chaque $P$ ainsi parcouru, on calcule sa distance avec les 7 suivants. On cherche la paire la plus proche. On retient la paire donnant la distance la plus petite. Soit $\delta_B$ cette distance.
  • À l'issue de cette recherche, on est certain que la paire la plus courte a été trouvée. Soit c'est la paire correspondant à $\delta$, soit c'est la paire correspondant à $\delta_B$.

Il pourra être utile de trier les points dès le départ selon les $x$ croissants.

Vous devez implémenter cet algorithme et le tester.

Puisqu'il s'agit d'optimiser un temps d'exécution, il sera bienvenu de prévoir une comparaison de temps d'exécution entre cet algorithme et un algorithme naïf.