Discussion :

[moooona]

Bonjour,
j'ai un ensemble des points qui ne sont pas uniforme, c'est à dire qu'ils sont dispersés aléatoirement dans l'espace (3D) .
J'ai besoin de déterminer les deux points les plus éloignés. J'ai pas trouvé une bonne méthode qui permet de déterminer ça. de plus je peux pas calculer les distances entre tous les points et déterminer la distance maximale car j'ai un nombre très énorme de points. je peux avoir même 1000000000 points.
J'ai réfléchi d'utiliser l'algorithme qui permet de déterminer le convex hull mais je suis pas sur que c'est la bonne méthode d'une part et s'elle va me donner ensuite un bon résultat.
Est ce qu'il y a quelqu'un qui peut m'aider.
Merci

[pseudocode]

J'ai réfléchi d'utiliser l'algorithme qui permet de déterminer le convex hull mais je suis pas sur que c'est la bonne méthode d'une part et si elle va me donner ensuite un bon résultat.

L'utilisation de l'enveloppe convexe est une bonne idée. Une fois l'enveloppe obtenue, il faut calculer la distance entre toutes les paires de points antipodales. La paire avec la plus grande distance donne les deux points les plus éloignés.

[Nebulix]

Je me demande bien d'où peuvent venir 10^9 points !
Et accesoirement à quelle loi de distribution aléatoire ils obéissent.
( ça devrait donner des idées sur la solution )
Enfin ce problème illustre bien l'intérêt de la notion d'ordre d'un algorithme.
Quel est celui de l'algo de l'enveloppe convexe ?

[moooona]

bonjour,
merci pour vos réponses

Enfin ce problème illustre bien l'intérêt de la notion d'ordre d'un algorithme.
Quel est celui de l'algo de l'enveloppe convexe ?

C'est pas claire ce que vous voulez dire.
J'ai pas trouvé un bon algorithme de convex Hull. Est ce qu'il y a quelqu'un qui peut m'aider dans ce point