Groupe de travail en Géométrie Discrète
Gdr IM
Le 21 novembre 2008 à l'Université de Savoie
Voilà le programme de la journée.
  • 8h45-9h00 : Accueil des participants
  • 9h00-9h50 : Exposé invité

    Valérie Berthé (LIRMM, Montpellier) :

    Géométrie discrète, pavages et dynamique symbolique

    [ Transparents PDF ]
    Le but de cet exposé est d'illustrer les liens qui existent entre dynamique symbolique et géométrie discrète à travers l'étude des plans arithmétiques discrets et de certains types de surfaces discrètes basées sur des pavages par losanges. En particulier, nous montrerons comment la notion de substitution (c'est-à-dire de morphisme de monoïde libre) permet d'aborder des problèmes variés tels que ceux de la reconnaissance, de l'engendrement ou de la connexité des plans discrets par le biais d'algorithmes de fractions continues multidimensionnels et de stratégies de réduction dans les réseaux.

  • Pause café
  • 10h20-12h20 : 4 exposés
    • Nicolas Ollinger, LIF, Marseille
      Pavage du plan par un nombre fixé de polyominos

      [ Transparents PDF ]
      Si la question de la pavabilité d'une figure finie par un jeu de polyominos admet de jolies solutions algébriques (groupes de tuiles, etc), la question de la pavabilité du plan tout entier est d'une autre nature. En effet, dans le cas général, étant donné un jeu fini de polyominos, cette question est indécidable, par réduction du problème de la pavabilité du plan par un jeu de tuiles de Wang (Domino Problem). Ce résultat est fortement lié à l'existence de jeux de polyominos qui ne produisent que des pavages apériodiques. Ainsi, dans le cas du pavage du plan par translation par un unique polyomino, il existe toujours un pavage extrêmement régulier et les polyominos pavant le plan se caractérisent syntaxiquement sur leur mot de contour comme des pseudo-hexagones (Beauquier-Nivat). Dans cet exposé, après avoir discuté les résultats précédents, nous nous intéressons à la pavabilité du plan par un nombre fixé de polyominos et nous obtenons plusieurs bornes nouvelles. Dans le cas du pavage par translations, il existe un jeu de 8 polyominos apériodique et le problème est indécidable pour les jeux de 11 polyominos. Dans le cas général du pavage par isométrie, il existe un jeu de 3 polyominos apériodique et le problème est indécidable pour les jeux de 5 polyominos.
    • Alain Daurat, LSIIT, Strasbourg
      Fréquences des motifs d'une discrétisation de courbe

      [ Transparents PDF ]
      On considère une fonction f défini sur [a, b], on quadrille le plan avec un maillage régulier de côté r. Pour une abscisse r*x donnée dans [a, b] on veut obtenir le point du quadrillage ayant cette abscisse en étant situé juste en-dessous de la courbe, de plus le point de maillage d'abscisse r*x retenu a pour ordonnée E(f(x*r)/r). On rappelle qu'un motif de taille m d'une courbe discrète est un ensemble de m points 8-adjacents de la courbe discrète. Dans cet exposé on montre que l'on peut calculer la limite de la fréquence d'un motif lorsque la résolution tend vers zéro pour certaine fonctione f.
    • Alex Esbelin, LAIC, Clermont
      Calcul de primitives et d'équations différentielles linéaires en nombre entiers par noyaux binômiaux
    • Christian Mercat, I3M, Montpellier
      Riemann-Roch discret

      [ Transparents PDF ]
      La structure des graphes a des propriétés réminiscentes de l'analyse complexe. Je présenterai deux versions d'un théorème de Riemann-Roch, l'un purement combinatoire, dû à Bacher, de la Harpe et Nagnibeda, et l'autre, plus proche en substance du théorème continu, s'appuyant sur la théorie des surfaces de Riemann discrètes.
  • Déjeuner
  • 14h00-14h50 : Exposé invité

    Christian Ronse (LSIIT, Strasbourg) :

    Segmentation connective contrainte et opérateurs idempotents sur les partitions

    [ Transparents PS gzipé ] [ Transparents PDF ]
    L'approche connective de la segmentation associe à toute image une connexion, de telle sorte que la segmentation de l'image est la partition des composantes connexes selon cette connexion. Des raisons tant théoriques que pratiques tendent à prendre en compte les partitions partielles (ne recouvrant pas nécessairement l'espace), et par conséquent les connexions partielles. Plusieurs exemples de segmentation connective (partielle ou non) sont décrits. Nous considérons ensuite la segmentation composée suivant une succession de connexions partielles, chacune appliquée au résidu de la précédente, et enfin la segmentation connective contrainte, où les composantes connexes sont filtrées en fonction d'un prédicat. Chaque type de segmentation connective (de base, composée ou contrainte) induit un type d'opérateur idempotent sur le treillis des partitions partielles.

  • Pause café
  • 15h20-17h20 : 3 exposés
    • John Chaussard, A2SI, Marne-la-Vallée
      Détection d'intersections de surfaces, avec garanties topologiques

      Résumé. Dans certaines application, comme l'étude d'images de fissures dans le béton, la détection d'intersections de surfaces est une étape importante. Nous disposons d'un objet composé de voxels, d'allure "surfacique", représentant les fissures, et nous voudrions le décomposer en "éléments simples" (surfaces, intersections de surfaces, ...). En général, la méthode utilisée pour détecter les intersections de surfaces d'un tel objet se décompose en deux étapes : un amincissement homotopique pour obtenir un objet fin, et une classification des points de l'objet afin d' obtenir sa decomposition en "éléments simples". Le problème de cette méthode, dans le cadre des voxels, est que nous n'avons pas de garantie topologique sur le résultat de la décomposition. Par exemple, l'ensemble des voxels classés comme étant l'intersection de trois surfaces ne formera pas nécessairement une courbe. Nous proposerons dans cet exposé d'utiliser le cadre des complexes cubiques : dans ce cadre, nous proposerons un nouvel algorithme d'amincissement homotopique adapté aux objets surfaciques, et nous verrons que la décomposition de l'objet en "éléments simples" est très simple à effectuer, et nous permet d'obtenir les garanties topologiques recherchées.
    • Yohan Thibault, A2SI/NII, Marne-la-Vallée/Japon
      Sur la densité des n-uplets pythagoriciens

      [ Transparents Powerpoint ]
      Résumé
    • Tristan Roussillon, LIRIS, Lyon
      Décomposition robuste de courbes discrètes en parties convexes et concaves

      [ Transparents PDF ]
      La décomposition du contour d'un objet en parties convexes et concaves fournit une description de la forme de l'objet. Toutefois cette mesure se doit d'être robuste au bruit afin d'éviter une sur-décomposition. Nous avons proposé un algorithme robuste, en ligne et linéaire en temps, de décomposition d'un contour en parties convexes et concaves. De plus, il est très simple à implémenter car il est basé sur un calcul d'enveloppe convexe et le théorème de Pick. Enfin, nous montrons que le même algorithme peut être utilisé pour décomposer de manière robuste le contour d'un objet en segments de droite, vus comme des portions du contour à la fois convexes et concaves, ce qui est une alternative aux algorithmes de reconnaissance de segments de droite existants.