{"id":1432,"date":"2017-02-02T07:45:30","date_gmt":"2017-02-02T07:45:30","guid":{"rendered":"http:\/\/pageperso.math.univ-toulouse.fr\/hippocampe\/?p=1432"},"modified":"2017-02-02T07:45:30","modified_gmt":"2017-02-02T07:45:30","slug":"lycee-saint-exupery-blagnac-distances","status":"publish","type":"post","link":"https:\/\/perso.math.univ-toulouse.fr\/hippocampe\/2017\/02\/02\/lycee-saint-exupery-blagnac-distances\/","title":{"rendered":"Lyc\u00e9e Saint Exup\u00e9ry (Blagnac) – Distances"},"content":{"rendered":"

Le mercredi 25 janvier, les 30 \u00e9l\u00e8ves d’une classe de terminale S du lyc\u00e9e Saint-Exup\u00e9ry arrivent \u00e0 l’Universit\u00e9 Paul Sabatier pour\u00a0participer \u00e0 un stage Hippocampe. Ils viennent s’initier pendant trois jours aux joies et aux difficult\u00e9s de la recherche. Leur professeur de math\u00e9matiques, un enseignant-chercheur et trois doctorants sont l\u00e0 pour\u00a0les aider si besoin dans ce travail.\"p1020072\"<\/p>\n

Le th\u00e8me du stage para\u00eet familier \u00e0 premi\u00e8re vue : les distances. Mais quand le plus court chemin d’un point \u00e0 un autre n’est pas la ligne droite, tout se complique !<\/p>\n

\u00a0Tra\u00e7ons des\u00a0ensembles de points \u00a0tous situ\u00e9s \u00e0 la m\u00eame distance d’un point donn\u00e9. Nous obtenons des\u00a0courbes appel\u00e9es courbes “d’isodistance”<\/em>. Dans le cas classique, comme sur la figure ci-contre, ces\u00a0ensembles sont des cercles. Les \u00e9l\u00e8ves ont obtenu la m\u00e9diatrice de deux points donn\u00e9s (trac\u00e9e en rouge), par la m\u00e9thode du “Fast Marching”.<\/p>\n

\"p1020092\"Mais si les courbes d’isodistance ne sont pas des cercles, comme par exemple\u00a0les courbes de relief\u00a0en montagne,\u00a0la m\u00e9diatrice n’est plus une droite. Sur la figure ci-contre, les \u00e9l\u00e8ves ont indiqu\u00e9\u00a0les courbes situ\u00e9es aux m\u00eames distances 1, 2, 3… de chacun de deux points donn\u00e9s A et B. Quand deux courbes\u00a0portant le m\u00eame num\u00e9ro ont un ou plusieurs points en commun, nous\u00a0obtenons des points de la m\u00e9diatrice.<\/p>\n

D’autre part, les \u00e9l\u00e8ves se sont appliqu\u00e9 \u00e0 montrer que le chemin le plus court pour aller du point A au point B (chemin trac\u00e9 sur la figure) passe par les points de tangence de deux courbes d’isodistance.<\/p>\n

\"sans-titre\"<\/a>Imaginons maintenant que nous nous d\u00e9pla\u00e7ons dans une ville quadrill\u00e9e de rues rectilignes et perpendiculaires les unes aux autres, entourant des p\u00e2t\u00e9s d’immeubles. Les \u00e9l\u00e8ves ont utilis\u00e9 des feuilles de papier quadrill\u00e9 pour mod\u00e9liser la situation. Ils ont cherch\u00e9 et trac\u00e9\u00a0les courbes d’isodistance sur ces\u00a0grilles cart\u00e9siennes o\u00f9 il n’est possible de se\u00a0positionner que sur les lignes des quadrillages. Ces courbes d’isodistance sont des points situ\u00e9s sur des carr\u00e9s (on ne peut pas se d\u00e9placer sur les diagonales du quadrillage, chaque petit carr\u00e9 repr\u00e9sentant un “immeuble”).
\nAvec cette contrainte, saurez-vous dire si le point appel\u00e9 D sur la figure ci-contre est plus pr\u00e8s de A ou de B ?<\/p>\n

\"voronoi-4-points\"<\/a>

D\u00e9limit\u00e9es en vert : cellules de Vorono\u00ef pour 4 points<\/p><\/div>\n

Revenons \u00e0 nos m\u00e9diatrices.\u00a0\u00c9tant donn\u00e9s deux points dans le plan, la droite qui est \u00e0 \u00e9gale distance de ces deux points, la m\u00e9diatrice, divise le plan en deux r\u00e9gions, chacune de ces r\u00e9gions contenant les points qui sont plus proches de l’un des points choisis au d\u00e9part que de l’autre. Lorsqu’on ajoute des points, le m\u00eame principe s’applique, et on obtient des\u00a0cellules contenant les points plus proches de l’un des points fix\u00e9s que de tous les autres. L’ensemble de ces cellules forment un diagramme de Vorono\u00ef dans le plan.<\/p>\n

\"delaunay\"<\/a>

Cellules de Vorono\u00ef et triangulation de Delaunay avec 9 points<\/p><\/div>\n

Les \u00e9l\u00e8ves vont ensuite tracer la triangulation de Delaunay : il s’agit de former un pavage (“partition”) de la surface d\u00e9limit\u00e9e par les points donn\u00e9s \u00e0 l’aide de triangles, de mani\u00e8re \u00e0 ce\u00a0que le cercle circonscrit \u00e0 chacun de ces triangles ne contienne aucun autre des points donn\u00e9s au d\u00e9part.<\/p>\n

On montre que, parmi toutes les triangulations possibles, celle de Delaunay maximise les plus petits angles. De cette mani\u00e8re, elle donne les triangles les moins aplatis possibles.<\/p>\n

\"deux-triangulations\"Sur la figure de gauche, il s’agit d’une triangulation de Delaunay pour 4 points. \u00a0Par contre, \u00e0 droite, le 4\u00e8me point appartient aux cercles circonscrits aux triangles, il ne s’agit pas d’une triangulation de Delaunay.<\/p>\n

Pour un nombre important de points, l’utilisation d’algorithmes devient n\u00e9cessaire autant pour la construction de plus courts chemins que pour celle de cellules de Vorono\u00ef et de triangulations de Delaunay. Ce fut l’occasion pour les \u00e9l\u00e8ves de b\u00e2tir certains algorithmes.<\/p>\n

Il existe de nombreuses applications \u00e0 ces notions : d\u00e9placements de robots, \u00e9tude de l\u2019\u00e9volution de cellules canc\u00e9reuses, d\u00e9termination de fronti\u00e8res sous-marines entre pays voisins, mod\u00e9lisation de r\u00e9seaux t\u00e9l\u00e9phoniques, \u00e9tude de la croissance des plantes…<\/p>\n

\"girafe1\"<\/p>\n

On a m\u00eame montr\u00e9 que le motif de la robe des girafes r\u00e9ticul\u00e9es correspond avec une approximation satisfaisante \u00e0 des cellules de Vorono\u00ef, explications \u00e0 l’appui…<\/p>\n

Apr\u00e8s un travail intense, passionnant et souvent passionn\u00e9, le dernier jour du stage a \u00e9t\u00e9 consacr\u00e9 \u00e0 la confection de posters. \u00a0Les \u00e9l\u00e8ves ont ainsi expos\u00e9 leurs r\u00e9sultats et les membres de l’institut de math\u00e9matiques ont pu leur poser des questions\u00a0au sujet :<\/p>\n

    \n
  • des plus courts chemins et de l’in\u00e9galit\u00e9 triangulaire,<\/li>\n
  • de d\u00e9placements dans les grilles cart\u00e9siennes,<\/li>\n
  • des graphes,<\/li>\n
  • de la triangulation de Delaunay,<\/li>\n
  • du trajet d’un rayon lumineux dans une fibre,<\/li>\n
  • du principe de Fermat.<\/li>\n<\/ul>\n\n\t\t