Ligne brisée sans croisement — Les-maths.net The most powerful custom community solution in the world

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]

Réponses

  • Bonsoir.

    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.

  • Bonjour à tous

    il faudrait peut-être éviter des vecteurs colinéaires, non ?

    Aldo
  • Bonjour à tous les deux.
    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]
  • Comme je ne trouve pas de contre-exemple , je généralise un peu .

    Dans le plan , peut-on toujours "enchaîner" $n$ vecteurs de directions différentes et de somme nulle pour former une boucle simple ?

    Domi125260
  • Bonjour.

    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.

  • Si on trie la liste par « arguments » croissants, je ne vois pas ce qui pourrait se passer.
  • Je me doute bien que ne suis pas le premier à lever ce lièvre, c'est un peu la raison pour laquelle j'ai proposé le problème ici. Enchaîner les vecteurs avec des angles croissants peut générer des croisements.
    Domi.

    [En typographie, on ne met jamais d'espace avant un point ou une virgule, mais toujours après. ;-) AD]
  • Ceci explique pourquoi je n'arrive à rien...

    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.

  • Domi a écrit:
    Enchaîner les vecteurs avec des angles croissants peut générer des croisements.
    Je veux bien un exemple, si ce n'est pas abuser.
  • >Math Coss

    A(3,0) B(0,1) C(-1, -1)

    devrait faire l'affaire.

    Aldo
  • Je ne comprends pas qui sont les vecteurs. Pas $\overrightarrow{OA}$ etc. puisque la somme doit être nulle.
    Avec trois vecteurs et une somme nulle, comment faire un croisement de toute façon ?
  • Bonsoir
    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
  • > Math Coss

    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.
  • Bon je crois que j'ai une solution un peu informelle ( mais qui devrait tenir la route ) du deuxième problème et donc du premier en utilisant l'argument de Math Coss . On construit la ligne en augmentant les arguments des angles , au moment où la ligne se recoupe , la somme des angles extérieurs est égale à 360° . On peut continuer à construire des côtés mais on ne pourra jamais revenir à l'origine car il faudrait faire un deuxième tour dans les même conditions mais la pente des nouveaux segments va restée coincée entre celle de la ligne de départ et celle de la ligne de rencontre . Ensuite le problème initial est facile à résoudre car il suffit d'ajouter l'opposé de la somme des vecteurs à la liste donnée avant de supprimer le segment ayant ce vecteur comme extrémités .

    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]
  • Domi : Comment peut-on faire confiance à ce que dit sur les maths quelqu'un qui est incapable de respecter les règles typographiques élémentaires (école primaire) et qui réclame le droit de ne pas les appliquer ?
    En fait, ce n'est qu'une mauvaise excuse de quelqu'un qui a pris une mauvaise habitude.
    Je plussoie AD.
  • Bonjour,

    Je plussoie également. A ta place, AD, je corrigerais et je fermerais. Bon, ce n'est que mon avis.

    Cordialement,

    Rescassol
  • Bonsoir.

    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.

  • Les réponses de Domi sont ce qu'elles sont mais ses questions sont en général dignes d'intérêt.
  • En effet, j'y vois de la susceptibilité ou de l'agacement et je ne sais pas s'il faut s'embrouiller tant que ça.

    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.
  • Il est clair que j'ai vu beaucoup trop de rouge dans la correction d'Alain mais je laisse les interventions de Gerard et de Rescassol à ce qu'elles sont . D'un autre côté je ne changerai pas mes habitudes et si elles dérangent vraiment le forum ou qu'elles donnent trop de travail à Alain , il faudra simplement les interdire .

    Domi
  • Bonsoir, juste une pensée. Le problème initial est vraiment ardu. Que je pense vrai et donc une conjecture. C'est bien la même classe de la conjecture du coureur solitaire (à mon avis). Même j'ai posté la question sur Mathoverflow, espérons que je tiens correctement...

    Edit c'était simple il fallait faire comme Domi suggère avec un vecteur de plus pour avoir une somme nulle.
  • Plus généralement si on se donne $n$ vecteurs de directions différentes et de somme nulle , peut-on toujours construire un polygone convexe $P_1P_2\cdots P_n$ de façon à ce que les vecteurs $\overrightarrow{P_1P_2} , \overrightarrow{P_2P_3} , \cdots , \overrightarrow {P_nP_1}$ soient exactement les vecteurs donnés ? Ce résultat semble tellement intuitif qu’il doit forcément exister un argument simple pour le justifier .

    Domi
  • Bonjour.

    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.

  • Je propose ceci :



    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
  • Bonjour,

    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 .
  • De quels angles parlons-nous ?
    Orientés, les plus fins ?
  • Les vecteurs OMi sont classés dans l'ordre inverse des aiguilles d'une montre,
    Le premier étant tel que langle Ox OM1 soit le plus petit
  • Je suppose que cedr parlait des mesures principales des angles orientés $(OM_i,OM_{i+1})$, qui sont toutes dans $\left[0,\pi\right[$ sauf éventuellement une qui est dans $\left[\pi,2\pi\right[$.
  • Oui je me suis trompé, les derniers angles sont orientés, et ce sont pas les angles $\alpha_i$ , mais les angles entre deux vecteurs consécutifs après avoir réordonné les vecteurs .
    et si il y a des vecteurs qui sont positivement colinéaires, les angles sont nuls .
  • Je n'ai sans doute pas compris les derniers échanges car je ne vois pas de différence avec ma première proposition, dont on m'a dit à raison qu'elle ne permettait pas de couvrir tous les cas.

    À bientôt.

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • Sans illustration , les constructions sont difficiles à suivre :-)

    En rangeant les arguments en ordre croissant dans $[0;2\pi[$ , j'ai bien l'impression que le polygone à droite est toujours convexe .

    Domi125324
  • Bonsoir, juste une chose l'argument de polygone convexe tient comme l'intuition de Domi, je n'ai pas vu l'idée qu'après la réponse ici https://mathoverflow.net/questions/400668/computational-conjecture-choices-for-a-path/400697#400697 (encore rien de commun avec le coureur solitaire....)
  • Bon, il ne reste plus qu'à transformer ces intuitions en preuves.

    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.

  • En effet , il serait bon de donner un peu de démonstration ( en français si possible ) .

    Domi
  • Les deux figures de Domi, juste au-dessus, là, me font penser à une sorte de « dual ».
    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).
  • Tout le monde est bien convaincu de la convexité du polygone. Formaliser une démonstration de ce fait est plus délicat.

    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)$.
  • Bonsoir GaBuZoMeu,

    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 ?
  • Bonsoir Dom,
    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 :


    210731102006135302.png
  • Ok.
    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-)
  • Bien vu GaBuZoMeu , c'est toujours simple après coup (tu)

    Je donne le problème initial ( vous allez y retrouver quelques connaissances ) Mikado .

    Domi
  • Désolé, je ne comprends pas.

    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
  • @Aldo : on a une ligne fermée ( car la somme des vecteurs est nulle ) .

    Domi
  • Merci 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
  • Bon ça va mieux j'avais un mauvais "Math Settings"

    Démo de GaBuZoMeu nickel !
  • Merci GaBuZoMeu.

    À bientôt.

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • Bonsoir,

    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.
    tri.ggb 16.3K
  • Merci Ludwig, ça me rappelle que je dois rapidement réinstaller géogébra !

    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
  • Bonjour 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 .

    Domi125436
  • Bonjour 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
  • En effet , c'est plus simple vu comme ça :-)

    Domi
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!