Géométrie

[ABDER]

Bonsoir tout le monde , svp je trouve des difficultés pr résoudre un probleme : on a plusieurs points et il est demandé de trouver "le point optimal" c'est le centre du cercle qui a le plus petit rayon dont les points appartiennent tous à son disque .

[Ben314]

Salut,
Ca me parait pas trivial comme problème.
C'est plutôt de l'informatique, c'est à dire une réponse sous forme d'algorithme de complexité pas trop grande que tu veut ?

[zygomatique]

salut

et on sait quoi sur les points : on a leur coordonnées ?

il me semble (vite fait) que le centre du disque ne devrait pas "être trop loin" du milieu du segment joignant les deux points les plus éloignés et le diamètre du disque "peu différent" de la distance joignant ces deux points ...

[Ben314]

Perso, j'ai (un peu) réfléchi avec une vision informatique du problème :
On se donne N points (i.e. leurs coordonnées) et on veut, avec un minimum de calculs, déterminer le disque en question.
Le truc que je sais (de mémoire, je suis pas sûr que je retrouverais l'algo. dans sa totalité...), c'est qu'en un temps O(N.log(N)) on peut trouver l'enveloppe convexe du nuage de points en question, donc on peut éventuellement supposer qu'on a l'enveloppe convexe (quitte à constater ensuite que ça sert à rien...)
Après, et sauf erreur, il y a deux cas de figure :
- Soit le bord du disque en question passe par 3 des points du nuage, (voire exceptionnellement plus) : c'est par exemple le cas si on a 3 points formant un triangle acutangle et où le disque est celui circonscrit au triangle.
- Soit le disque en question a pour diamètre 2 des points du nuage : c'est par exemple le cas si on a 3 points formant un triangle obtusangle.
Dans le deuxième cas, il me semble bien que les deux points en question sont forcément ceux donnant le diamètre du nuage, mais dans le premier cas, je suis pas du tout sûr que les deux points du diamètre fassent forcément parti des 3 du bord du disque.

[zygomatique]

oui c'est peut-être mieux de raisonner avec trois points (ou il y en a plus mais ils appartiennent au bord du disque) ....

merci

[Robot]

C'est un problème algorithmique classique. Googler "Smallest enclosing circle), qui donne par exemple :
http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

[zygomatique]

merci pour le lien ...

mai en anglais je regarderai tout cela plus tard .... avec du temps ....