Les deux points les plus proches

Soit {E} une partie finie de {\mathbb{R}^{2}.} On veut déterminer deux points de {E} minimisant la distance entre points distincts de {E.}

L’ensemble {E} sera représenté par un tableau {t} de taille {n\ge 2} formé de couples distincts de flottants.

La fonction dist calcule la distance entre deux points de {\mathbb{R}^{2}.}

8.4.1 Algorithme naïf

Une méthode très na ̈ive consiste à considérer toutes les paires de points distincts de {E.}

C’est ce que fait la fonction plus_proches_naif, qui renvoie un couple de points distincts réalisant la distance minimum :

La complexité de cette fonction est de l’ordre du nombre de paires de {E,} donc de l’ordre de {n^{2}.}

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :