Étalement maximal de plusieurs points

Question

J'ai un groupe de points (x, y) et j'ai besoin de trouver la distance entre les deux qui sont les plus éloignés.

Quel est le moyen le plus efficace de trouver ceci?

Merci

Answer 1

Eh bien, compairing chaque point contre tous les autres points est certainement pas efficace.

Le moyen le plus efficace consiste à trouver la coque convexe, qui est le polygone convexe (aucun angle> 180) entourant tous les points. Après cela, vous trouverez les points les plus éloignés sur la coque, en utilisant des paires antipodales.

algorithme décrit ici:

http://www.seas.gwu.edu/~simhaweb/cs153/lectures/module1/module1.html