Ligne brisée sans croisement
Bonjour à tous.
Je me suis posé une question naïve à propos d'un problème de minimum.
On se donne $n$ vecteurs du plan de directions différentes et de somme non nulle. On construit une ligne brisée en partant d'un point $P_0$ puis en choisissant un des vecteurs $\overrightarrow{u}$ pour obtenir un point $P_1$ tel que $\overrightarrow{P_0P_1}=\overrightarrow{u}$. On renouvelle l'opération à partir de $P_1$ et d'un nouveau vecteur $\overrightarrow{v}$ pour obtenir un point $P_2$ tel que $\overrightarrow{P_1P_2}=\overrightarrow{v}$ et ainsi de suite jusqu'à $P_n$ après épuisement des vecteurs. Est-il toujours possible de choisir un bon ordre pour les vecteurs de façon à ce que la ligne brisée $P_0P_1\ldots P_n$ ne se recoupe pas ?
Merci d'avance pour vos réponses :-)
Domi
PS : je ne sais pas si c'est d'une quelconque utilité mais dans le problème initial les vecteurs sont normés.
[En typographie, on ne met jamais d'espace avant un point ou une virgule, mais toujours après. ;-) AD]
Je me suis posé une question naïve à propos d'un problème de minimum.
On se donne $n$ vecteurs du plan de directions différentes et de somme non nulle. On construit une ligne brisée en partant d'un point $P_0$ puis en choisissant un des vecteurs $\overrightarrow{u}$ pour obtenir un point $P_1$ tel que $\overrightarrow{P_0P_1}=\overrightarrow{u}$. On renouvelle l'opération à partir de $P_1$ et d'un nouveau vecteur $\overrightarrow{v}$ pour obtenir un point $P_2$ tel que $\overrightarrow{P_1P_2}=\overrightarrow{v}$ et ainsi de suite jusqu'à $P_n$ après épuisement des vecteurs. Est-il toujours possible de choisir un bon ordre pour les vecteurs de façon à ce que la ligne brisée $P_0P_1\ldots P_n$ ne se recoupe pas ?
Merci d'avance pour vos réponses :-)
Domi
PS : je ne sais pas si c'est d'une quelconque utilité mais dans le problème initial les vecteurs sont normés.
[En typographie, on ne met jamais d'espace avant un point ou une virgule, mais toujours après. ;-) AD]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Dans l'épure de Cremona, il est question de ce genre de choses.
Je n'ai pas de preuve, mais il me semble bien qu'il est toujours possible de réarranger les vecteurs pour éviter les croisements, notamment en les triant en ordre croissant ou décroissant d'angle par rapport à une origine des angles fixée.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
il faudrait peut-être éviter des vecteurs colinéaires, non ?
Aldo
Oui Aldo, les vecteurs sont non nuls et de directions différentes.
Domi.
[En typographie, on ne met jamais d'espace avant un point ou une virgule, mais toujours après. ;-) AD]
Dans le plan , peut-on toujours "enchaîner" $n$ vecteurs de directions différentes et de somme nulle pour former une boucle simple ?
Domi
Oui, il doit être possible de le prouver par récurrence en considérant des croisements et en montrant que l'ordre des vecteurs, suivant le critère que j'ai donné, n'est pas respecté.
Par contre, désolé mais je n'ai pas encore trouvé de preuve complète, j'ai juste les lignes directrices plus haut comme guide actuellement.
Cela m'étonnerai quand même que personne n'ait pensé à faire une preuve de ce genre.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Domi.
[En typographie, on ne met jamais d'espace avant un point ou une virgule, mais toujours après. ;-) AD]
Autre approche : à partir d'une origine commune, regrouper tous les vecteurs, en prendre un comme vecteur de départ et appliquer des translations aux autres vecteurs suivant un critère à définir.
Quand un croisement apparaît, c'est que le vecteur a été mal choisi.
Le problème est qu'il y a un nombre plus qu'exponentiel de configurations possibles à tester, mais pour les exemples que j'ai fais, cela se passait bien la plupart du temps car "on voit" celui qu'il faut ajouter ensuite.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
A(3,0) B(0,1) C(-1, -1)
devrait faire l'affaire.
Aldo
Avec trois vecteurs et une somme nulle, comment faire un croisement de toute façon ?
J’ai cru que le problème était de relier des points (du coup je ne voyais pas ce que venait faire la somme nulle des vecteurs) pour obtenir une « étoile » en gros (ne pas que ça se croise).
Mais là avec ton dernier message, Domi, je viens de comprendre.
Question, les deux problèmes (points, vecteurs) sont-ils liés ?
Je ne sais en résoudre aucun des deux. Même si « je vois mieux » pour les points.
Cordialement
Dom
Désolé je n'avais pas compris que tu étais déjà passé au deuxième énoncé. Mon contre exemple n'en est donc pas un.
Il faudra sans doute que j'illustre
Domi
PS : Pour [AD] : inutile de s'énerver , j'ai bien compris le message depuis longtemps , je n'ai pas le droit de l'ignorer ?
[Que fais-tu quand un élève décide d'ignorer tes consignes ? (td) AD]
[Je ne suis pas ton élève et il me semble que mon manque de respect pour les règles typographiques en usage aujourd'hui agresse bien peu de monde . Domi]
En fait, ce n'est qu'une mauvaise excuse de quelqu'un qui a pris une mauvaise habitude.
Je plussoie AD.
Je plussoie également. A ta place, AD, je corrigerais et je fermerais. Bon, ce n'est que mon avis.
Cordialement,
Rescassol
Je vous en supplie, ne fermez pas ce sujet-ci avant que l'on ait formalisé le critère de réarrangement à appliquer sur les vecteurs pour faire un polygone sans croisements, cela m'intéresse vraiment.
Je vous en prie.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Domi, tu sais bien que AD fait un boulot très chronophage pour rendre chaque message plus lisible.
C'est dommage d'être piqué au vif alors qu'il n'est selon moi jamais agressif et plutôt très bienveillant et patient (on ne peut pas en dire autant d'autres intervenants sur le thème de la mise en forme des messages...).
Ce fil mérite selon moi de rester ouvert car il est d'un intérêt mathématique.
Domi
Edit c'était simple il fallait faire comme Domi suggère avec un vecteur de plus pour avoir une somme nulle.
Domi
Non, ce n'est pas si sûr.
Par contre, parler de conjecture similaire au coureur solitaire, j'ai du mal à cerner l'objectif si ce n'est d'essayer de décourager.
À moins que quelqu'un n'apporte un article, pour l'instant on ne sait même pas qui à pu s'intéresser à ce sujet avant Domi.
Pour ma part, quand j'ai fais des épures de statique, je ne me suis jamais posé cette question mais j'ai toujours su faire des polygones convexes.
En désespoir de cause, on pourrait éventuellement utiliser la formule du calcul de l'aire d'un polygone en réarrangeant les sommets suivant une procédure de maximisation de l'aire, mais cela ne m'enchante pas et je préférerais vraiment une preuve par récurrence sur le nombre de vecteurs en réorganisant leur ordre, mais je butte sur le critère suffisamment général pour traiter tous les cas.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
On a donc n vecteurs de somme nulle.
On les classe par ordre d'argument croissant.
Partant de l'origine O, on construit la ligne brisée avec les vecteurs NE puis NO.
Soit A l'extrémité de cette ligne brisée. Jusque là, pas de risque de croisement.
La ligne est convexe, dans le sens que le polygone qu'elle forme avec le segment AO est convexe.
Maintenant, à partir de A, nous plaçons les vecteurs SO puis SE.
Nous allons former de manière identique une 2e ligne, convexe dans le même sens que précédemment.
Supposons que l'un des vecteurs MN croise la première ligne.
La 2e ligne brisée étant convexe, le point O est définitivement à l'extérieur de cette ligne.
Ce qui contredit l'hypothèse que la somme des vecteurs soit nulle.
Pour être clair : quand je dis que la ligne brisée est convexe, cela signifie que la polygone formé en lui rajoutant le segment reliant point initial et point final est convexe.
Aldo
Je pense que l'on peut y arriver par étapes:
1) on prend un vecteur $u_0$
2) on donne les angles que forment ces angles avec le vecteurs $u_0$, cela donne le les angles $\alpha_i=(u_0,u_i)$
et on prend ces angles dans $[0;2\pi[$ ,
et on réindexe les vecteurs $(u_i), i\in1....n$ de façon à ce que les angles $(\alpha_i), i\in1....n$ soient dans l'ordre croissant
3) on définit les point $P_i$ en partant de la pointe de $u_0$
la ligne ne sera pas brisée car le polygone obtenu est convexe, pourquoi ? si les angles sont ordonnés, ils sont tous aigus sauf 1 au plus, si il y a plus de deux angles obtus on a une contradiction puisque les angles sont dans $[0;2\pi[$ . Bonne journée .
Orientés, les plus fins ?
Le premier étant tel que langle Ox OM1 soit le plus petit
et si il y a des vecteurs qui sont positivement colinéaires, les angles sont nuls .
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
En rangeant les arguments en ordre croissant dans $[0;2\pi[$ , j'ai bien l'impression que le polygone à droite est toujours convexe .
Domi
Sur le mathoverflow, ils donnent cela comme des évidences, mais aucune référence (à ce que j'ai vu).
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Domi
En effet, les flèches sont dans le même ordre sur la gauche (vecteurs avec la même origine) que sur le droite (polygone convexe).
Mais je ne sais pas formaliser cette dualité (et ce n’est peut-être qu’une intuition foireuse).
Une tentative :
On a $n$ points distincts $M_0,M_1,\ldots,M_{n-1},M_n=M_0$ dans le plan affine euclidien orienté ($n\geq3$). On suppose que les vecteurs $u_{i+1}=\dfrac{\overrightarrow{M_iM_{i+1}}}{\Vert M_iM_{i+1}\Vert}$ sont rangés dans le sens direct sur le cercle unité pour $i=0,\ldots,n-1$. Alors $M_0M_1\dots M_{n-1}M_0$ est le bord d'un polygone convexe.
Schéma de démonstration par récurrence sur $n$.
- Initialisation pour $n=3$
- Ètape de récurrence de $n-1$ à $n$ pour $n>3$ : on supprime le dernier point $M_{n-1}$. Alors $\dfrac{\overrightarrow{M_{n-2}M_{0}}}{\Vert M_{n-2}M_{0}\Vert}$ est sur l'arc de cercle entre $u_{n-2}$ et $u_1$ qui contient $u_{n-1}$ et $u_n$. On applique l'hypothèse de récurrence pour obtenir le polygone convexe $M_0M_1\ldots M_{n-2}M_0$, le triangle $M_{n-2}M_{n-1}M_0$ est à l'extérieur de polygone convexe et du bon côté des droites $(M_{n-3}M_{n-2})$ et $(M_0M_1)$.
J’essaye de comprendre (je hiérarchise mon message)
a) on range les $u_i$ de sorte qu’ils forment des aiguilles d’une horloge (le cercle unité).
b) on a normalisé (à ce propos, c’est « lourd » mais il manque une flèche au dénominateur, à l’intérieur de la norme, non ? ou alors on écrit plus simplement, sans rien, ni flèche ni norme $M_iM_{i+1}$)
c) le fait que ça reste convexe : (j’ai une autre idée)
le cercle disque l’est [convexe] et à chaque fois on l’intersecte avec un demi-plan.
Ça me rappelle mes années « méthode du simplexe ».
d) on montre que le polygone tracé est convexe mais par contre je vois plutôt « la figure de gauche » (avec les vecteurs de norme 1) mais pas du tout la figure de droite.
Suis-je à côté de la plaque ?
Comme la norme ne dépend pas du sens dans le quel on va, je n'ai pas mis de flèche. Mais tu as compris de quoi il retourne.
Pour la suite, je ne comprends pas ce que tu écris (en particulier ("le cercle disque l’est [convexe] et à chaque fois on l’intersecte avec un demi-plan").
Un petit schéma pour illustrer ce que je voulais dire :
J’étais tout de même à l’ouest.
J’ai compris le départ (les aiguilles de mon horloge qui sont les $u_i$).
Puis très maladroitement je n’ai pas lu ce que tu avais écrit mais interprété tout autre chose… et j’ai perdu le lien avec le sujet du fil.
Bref, n’importe quoi.
PS : ma phrase sur les convexes sert à démontrer autre chose que ce qu’on veut et de beaucoup plus trivial.
Quand on place des points sur un cercle et qu’on les relie dans l’ordre suggéré par le sens direct (ordre de parcours sur le cercle), ça forme un polygone convexe.
Oublions ma méprise. 8-)
Je donne le problème initial ( vous allez y retrouver quelques connaissances ) Mikado .
Domi
L'énoncé est bien celui-ci
"Dans le plan , peut-on toujours "enchaîner" n vecteurs de directions différentes et de somme nulle pour former une boucle simple ?"
Que la ligne brisée ait une forme convexe (ça tourne toujours dans le même sens), c'est OK, mais je ne vois pas la preuve qu'il n'y a pas de croisement. Merci de m'expliquer svp...
Aldo
Domi
effectivement, ça saute aux yeux. Néanmoins, après croisement, la ligne peut continuer jusqu'à se fermer (un tour de plus).
Mais en fait j'avais un problème de notation dans la démo de GaBuZoMeu,
que veux dire les vecteurs ui+1=MiMi+1 ..............
Mais c'est ok, la démo par récurrence montre qu'on a un polygone convexe, donc sans croisement.
Aldo
Démo de GaBuZoMeu nickel !
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Ci-joint un petit applet GGB : cinq points variables (en bleu), le sixième calculé pour que la somme vectorielle soit nulle. Ces six points sont ensuite placés dans une liste $l_1$, et sont triés suivant leurs arguments, en deux étapes :
$l_2=$Trier(Séquence((arg(Elément(l1, i)) + Si(arg(Elément(l1, i)) < 0, 6.28319, 0), i), i, 1, Longueur(l1))),
puis $l3=$Séquence(Elément(l1, y(Elément(l2, i))), i, 1, Longueur(l1)) (liste $l_1$ triée).
Les listes $l_4$ et $l_5$ correspondent à la construction du polygone convexe, à partir du point de base $M$, variable.
On peut sûrement faire mieux, en particulier ajouter des points automatiquement dans la première liste.
Voici une petite démonstration toute simple :
- On ordonne les vecteurs de manière circulaire en les centrant sur une origine commune, dans le sens trigo.
- Tout vecteur partage le plan en deux demi-plans : gauche et droite.
- On commence la ligne brisée par un des vecteurs puis on applique au bout de chaque vecteur le vecteur suivant (selon l'ordre pré indiqué).
- Quel que soit Vd le vecteur de départ, on va appliquer d'abord tous ceux qui pointent vers le demi plan gauche de Vd puis tous ceux qui pointent vers la droite de Vd.
- Tant qu'on applique des vecteurs visant à gauche, il ne peut pas y avoir de croisement.
- Supposons qu'il y ait un croisement : Vk coupant Vi avec k>i.
- Construisons la ligne brisée en prenant Vi comme premier vecteur. Soit Mi l'origine de Vi.
- Puisqu'il y a croisement au moment de poser Vk, c'est que Vk vise à droite de Vi. Soit Pk l'extrémité de Vk
- Or, nous avons vu que les vecteurs visant à gauche de Vi ont déjà tous été utilisés.
- Du point Pk se trouvant dans le demi plan de droite de Vi, on ne pourra plus rejoindre le point Mi puisqu'il ne reste que des vecteurs visant le demi plan à droite.
- Ce qui contredit l'hypothèse de somme nulle des vecteurs.
Bon, j'ai un peu décortiqué pour être sûr de ne rien oublier...
Aldo
Je ne vois rien à redire à ta démonstration sauf que tu montres simplement que la boucle est simple mais on doit pouvoir l'adapter sans mal avec des demi-droites à la place des vecteurs pour justifier la convexité .
Sinon , je reste un peu sur ma faim , le polygone est construit avec des arguments croissants , il y doit avoir une explication simple avec les angles orientés des vecteurs 12 puis 23 , 34 , ... En effet tout retournement d'un de ces angles va créer une concavité dans le polygone .
Domi
plutôt que de voir en termes d'angles croissants, il me semble plus simple de considérer l'ordre des vecteurs. Avec la remarque que Vi+1 est toujours dirigé vers le demi-plan gauche de Vi, il n'y a aucun risque de concavité (pas de point d'inflexion).
Bonne journée !
Aldo
Domi