Recherche:

... et c'est ce qui nous intéresse, non ? :)


Pas exactement non, mais à peu de chose près oui.
Ca reste un gain de temps, et donc une optimisation (pour en revenir à la question de victor).

Ca reste du O(N²) mais tu divises quand même par deux le nombre d'itérations, ce qui n'est pas rien.
La complexité c'est beau, mais ça ne dit pas tout... :)

Puisque tu utilises des comparaisons de distances, tu peux te passer de calculer la racine carrée, et juste sommer le carré des coordonnées. C'est pas si lourd que ça à calculer ;)

Beh ca dépend de la distribution de points. Si tu sais qu'elle est bien uniforme, tu peux utiliser ta solution sans problème je pense. A vérifier ;)

Ta seconde méthode doit bien fonctionner si la répartition des points est relativement uniforme.

Ca ne fonctionnera pas dans ce genre de situations :
http://babystyle.free.fr/dist_pt.png
...