"Reliage" de points le plus court

[invite6b900f7a]

Bonjour,

Alors, voilà la colle, j'ai un nuage de point dans un plan 2D. Comment les reliés tous de manière à ce que la "corde" qui les relient soit la plus courte ?
-----

[invite551c2897]

Bonjour.
C'est le pb du voyageur de commerce ?

[invite986312212]

Le voyageur de commerce c'est la recherche d'un circuit de longueur minimale. Si on cherche à relier les points par des arcs de longueur cumulée minimale, c'est un problème beaucoup plus facile appelé "minimum spanning tree". Ca revient à la recherche de la distance ultramétrique maximale parmi celles qui sont inférieures à la distance euclidienne (entre ces points).