salut

une idée de récurrence (sans aucune certitude que cela convienne) selon le principe barycentrique :

je considère les quatre triangles ABC, BCD, CDE et EAB pour lesquels je construis les quatre points correspondant au minimum de trajet

je considère alors le point P correspondant au minimum de trajet pour ces quatre points

bon maintenant ta figure montre un pentagone convexe ABCDE
peut-être qu'il y a mieux si ce pentagone n'est pas convexe ...

pour faire avancer le schmilblick ... ou pas ...

PS : c'est pourquoi je ne blanke pas ... car on est dans de la recherche collective !!!

damned !! j'ai oublié le triangles DEA ...

Bonjour,
sans oublier le triangle DEA ,carpediem est sur la bonne piste...
Je pense qu'il faut utiliser les propriétés vectorielles.

le problème (d'où le "damned") est que en faisant ça on ne diminue pas le nombre de points
on transforme le pb du point P pour 5 points en un problème d'un point P pour 5 nouveaux points. qui n'ont à priori aucune raison de partager le même P minimum que les 5 points de départ.

on voit avec l'exemple de 3 et 4 points que les solutions pour ces deux problèmes n'ont absolument aucun rapport entre elles
ce qui suggère qu'une récurrence sur le nombre de points ne semble pas particulièrement prometteuse.

si on cherche une méthode itérative par approximations successives, il serait bon que cette méthode fonctionne pour 3 et 4 points, dont on connait les solutions, ce qui permet de valider la méthode.

mathafou a permuté les points D et E ... pour trompé l'ennemi, c'est pourquoi j'ai oublié un triangle !!

en fait ça fait toujours cinq triangles donc cinq points donc :

soit on recommence le même principe avec ces cinq nouveau points
vu que ces 5 nouveaux points sont dans l'enveloppe convexe, la taille des pentagones successifs tend vers 0 donc à la limite on a le point voulu

soit on applique le même principe mais en considérant plutôt les quadrilatères ABCD, BCDE, CDEA et DEAB pour lesquelles on connait la solution ...

PS : quand j'ai posté je n'avais pas vu le msg de mathafou

je relève les mêmes idées que lui ... et ma proposition reste toujours intuitive

_{"pour tromper l'ennemi"
non, parce que mes points ont été rajoutés l'un après l'autre au fur et à mesure des 3 figures fournies dans le même fichier, l'ordre alphabétique n'a aucun rôle dans l'affaire}

considérer les 5 quadrilatères et leur solution revient à considérer le pentagone "interne" formé par les 5 diagonales.



la méthode ne semble valable que si on peut prouver que le P pour ABCDE est le même que pour FGHIJ sinon on convergerait vers un autre point que celui cherché.

cela n'est pas le cas pour passer de 3 à 4

P4 est le vrai pour (A,B,C,D)
P3 celui pour (A,B,C), P3a pour (B,C,D), etc
et P'4 P4 le vrai pour (P3,P3a,P3b,P3c)
pourquoi le serait-ce pour passer de 4 à 5 ?

Bonjour à tous

Je débarque un peu tard ( humour ) , avec Mathafou c'est un cyclone permanent . Le problème du triangle est connu celui du quadrilatère un peu moins . Il y a une solution simple ?
Imod

le quadrilatère est encore plus simple que le triangle : c'est le point d'intersection des diagonales par simple application de l'inégalité triangulaire

mathafou : je me doute bien que c'est venu au gré de la construction !!

pour 4 points on peut remarquer que les coordonnées barycentre de P sont rationnelles
pour 3 points elles ne le sont pas car elles font intervenir l'angle de 120 °
peut-être est-ce une/la raison pour laquelle on ne peut pas passer de 3 à 4 ?
qu'en est-il pour 5 points : arrivera-t-on à une même situation que pour 3 points ou le point P possède à nouveau des coordonnées barycentriques rationnelles ?

pour le quadrilatère (convexe) oui, une solutions simple. (très simple même d'où l'intérêt je pense de carpediem pour des quadrilatères au lieu des triangles)
le problème est ouvert (mais sait on jamais) pour plus de 4 points.

par le calcul on peut estimer un point "meilleur" que le P actuel en se déplaçant au point annulant (dL/dx, dL/dy) "à peu près"
(= en assimilant les courbes L(x) et L(y) à des paraboles)



par exemple déplacement en y vers un point P' meilleur, annulant dL/dy à x constant
c'est un peu ce qu'on fait "à la main" en déplaçant P alternativement en x et en y vers un point meilleur.

on converge ainsi rapidement vers la solution quel que soit le nombre de points.
mais bon ... on préfèrerait arriver directement dessus comme pour 3 et 4 points !

euh ... tout au moins vers un optimum local, car il pourrait y avoir plusieurs bosses à la surface L(x,y)

ne voyant aucun moyen géométrique "simple" alors en furetant j'ai trouvé cela : qui propose un procédé constructif récurrent et convergent à une condition près

waouu. je pense que cet article fait le tour de la question.
en fait j'étais en train de réinventer l'algorithme de Weiszfeld avec mes dérivées partielles

Une animation Geogebra que je venais de terminer : Geogebra



de 3 à 10 points sont créés et déplaçables, le point P peut être déplacé à la main pour chercher le minimum
pour n = 3 et n = 4 les solutions exactes sont affichées

l'algorithme est exécuté pas à pas (bouton 1 Step) ou 10 pas à la suite (bouton Start)
Le bouton Stop abandonne cette série de 10 prématurément au besoin. (utile surtout si j'en avais demandé plus de 10, ou sans fin)

PS : géogébrea et l'algorithme en général n'aime pas trop les divisions par 0,
dans ce cas il se plante et fait disparaitre tous les élément calculés (vu que le nouveau point n'existe pas, se placer dessus donne un point P qui n'existe plus)
il faut relancer l'appli pour recréer le point P.
comme dirait l'autre "y'a quelque chose qui cloche là dedans, j'y retourne immédiatement"
(Vian in "la Java des bombes atomiques")

il suffit de rester sur place si P' n'existe pas (si P est à une étape en l'un des points fixés)
en particulier c'est ce qu'il se passe "souvent " si pour trois points l'un des angles du triangle est > 120°, vu que le minimum est justement en ce sommet.

mise à jour de l'appli dans la foulée.
(rajouter juste deux "Si" dans le script !)

tiens d'ailleurs je proposais déjà ce lien dans le fil Point minimisant les distances d'un nuage de points

mon intuition d'aujourd'hui n'est donc pas si mauvaise que celle "d'hier" ...
peut-être parce que hier j'avais déjà pensé à une méthode analytique avec des coordonnées ...