Journées de Géométrie Algorithmique 2002

14 - 18 octobre




LORIA INRIA GDR ALP du CNRS IFP
Université UHP, Nancy 1 Ecole Doctorale IAEM CEA


Résumés des cours




Steve Wismath (lundi 14, 9h30-10h30 et 11h-12h) 


Straight line drawings of graphs in three dimensions

Straight-line crossing-free drawings of graphs have been well studied in two dimensions. In three dimensions, we draw a given graph by locating its vertices at integer-valued grid points and representing its edges as straight line segments that do not cross. Any graph can be so drawn but the volume (of its bounding box) grows quickly; for complete graphs with n vertices, the volume is Theta(n3). For classes of sparser graphs, only a few non-trivial volume bounds are known. In particular, the situation for planar graphs is an interesting open problem since in two dimensions this case is very well studied and the area is known to be Theta(n2). To date, in three dimensions, no o(n2) volume result has been obtained for planar graphs although outerplanar graphs have been shown to require only O(n) volume.

In this talk I will outline some of the interesting results on three-dimensional straight-line graph drawing and discuss some of the current open problems in this area.




Fabrice Rouillier (mardi 15, 9h-10h30) 
 


Outils pour l'étude des zéros réels de systèmes algébriques

Le but de l'exposé est de présenter quelques algorithmes performants, utilisant principalement du calcul exact, pour l'étude des zéros réels des systèmes algébriques.

Ce type d'algorithmes, dont la sortie est complètement certifiée, permet d'obtenir des résultats souvent impossibles à établir par des méthodes purement numériques : existence de zéros réels, nombre de zéros réels, isolation des coordonnées des solutions, multiplicités.

Le cours sera effectué sur la base d'un ou deux exemples pratiques, issus de problèmes académiques ou industriels. Les outils (et rappels théoriques nécessaires) seront introduits un à un au cours de la résolution de ces exemples.




Katrin Dobrindt (mardi 15, 11h-12h) 
  


Simulation numérique avec Autoform et ses applications géométriques

Dans une première partie, je présenterai le métier d'emboutissage et ses enjeux. L'emboutissage est un procédé de fabrication : il s'agit d'une opération de mise en forme à froid des métaux par un outil de presse. Dans l'industrie automobile, les pièces de carrosserie sont embouties, mais aussi des composants du moteur, la boîte de vitesse.

Puis je vais présenter AutoForm, ses logiciels et ses clients. AutoForm Engineering est une société de haute technologie spécialisée en simulation numérique des opérations d'emboutissage. Ses logiciels sont utilisés mondialement par tous les constructeurs d'automobile (comme Audi, BMW, Chrysler, Daewoo, Ford, General Motors, Honda, Jaguar, Mercedes, Nissan, Opel, Peugeot, Porsche, Renault, Toyota, Volkswagen, et Volvo) et par leurs fournisseurs (outilleurs, producteurs d'acier/aluminium).

Finalement, je poserai les problèmes géométriques. Les problèmes géométriques rencontrés lors d'une simulation numérique sont multiples : principalement la génération des maillages qui doivent répondre aux demandes numériques, mais aussi des opérations simples comme enveloppe convexe, localisation de points, alpha shape, inside-out test...



Luc Devroye (mercredi 16, 9h30-10h30 et 11h-12h) 
    


Random multidimensional data structures

Operations to be performed in high dimensions include search, range search, nearest neighbor search, point location, and insert/delete. We discuss a number of randomized data structures for these tasks, including several brands of k-d trees and k-d quadtrees, as well as some graphs that partition the space.



Rémi Langevin (jeudi 17, 9h-10h30 et 11h-12h30)  
   


Introduction à la géométrie intégrale

La géométrie intégrale a commencé avec Buffon, Cauchy et Crofton qui ont montré que la longueur d'une courbe plane est proportionnelle à la ``moyenne'' du nombre de points d'intersection avec une droite. Faire de la géométrie intégrale, c'est d'abord couper (de ``toutes'' les façons possibles), projeter (sur tous les sous-espaces possibles) pour obtenir une information globale sur une sous-variété de l'espace euclidien.

Nous en profiterons pour montrer comment les courbures d'une sous-variété ou d'un polyèdre s'interprètent avec ce point de vue. Ceci permet d'obtenir des résultats globaux du type : une topologie compliquée implique une géométrie compliquée.



Michel Pocchiola (vendredi 18, 9h-10h30) 
    


Pseudo-triangulations et applications

L'objectif de cet exposé est de montrer comment les pseudo-triangulations interviennent dans la résolution de deux problèmes élémentaires de géométrie algorithmique : le calcul des graphes de visibilité et la déformation de mécanismes plans articulés (Carpenter's rule problem).


 


David Bremner (vendredi 18, 11h-12h30) 
    


Realization problems for convex polytopes (and relatives)

A convex polytope is the bounded intersection of a set of halfspaces in Rd). The faces of a convex polytope P are the intersections with P of supporting hyperplanes; ordered by inclusion, these form the face lattice of P. Polytope realizability questions take the form ``Given (part of) a lattice, is it realizable as (part of) the face lattice of some d-dimensional convex polytope?'' The most famous result about realizability for convex polytopes is Steinitz's Theorem: every 3-connected planar graph is realizable as the skeleton (vertex-edge graph) of a 3-dimensional polytope, and conversely every convex 3-polytope has a planar 3-connected skeleton. As is so often the case, the situation in higher dimensions is more complicated. In four (and larger) dimensions, polytope realizability has recently been shown to be equivalent to the existential theory of the reals, and are thus (at least) NP-hard. Matroid polytopes are combinatorial abstractions of point sets in convex position. A natural approach to polytope realizability questions is to first consider realizing a lattice as a matroid polytope (matroid polytope realizability), and then to test the result (if any) for realizability as a point set. In this talk I will survey recent theoretical results of Richter-Gebert, Mnëv, and Tschirschnitz, and discuss my own experiments with matroid polytope realizability, as well as the motivation for these experiments, the famous Hirsch conjecture on the diameter the skeleton of a convex 3-polytope.



Résumés des exposés



 


Sylvain Théry (lundi 14, 12h00-12h30) 
     


Une structure topologique optimale pour les maillages triangulaires manifold

In geometric modeling, the boundary representation is the classical method to describe the shape and structure of an object in a 3D space. There are lots of topological models in the literature which allow a hierarchical structuring of objects in vertices, edges and faces, and manage the neighbourhood relation between them. In some applications like human organs reconstruction from CT-scan, objects can be represented by oriented manifold triangular meshes. We introduce a new simplified topological model adapted to this case. It is very simple, low memory consuming, easy to implement, and we show that it allows the same operations than more general models. The classic indexed face set structure of VRML97 for example can be enhanced with our topological structure very easily.


 


Philippe Guigue (lundi 14, 16h30-17h) 
      


Une méthode rapide pour tester l'intersection de deux triangles en 3D

Nous proposons une nouvelle méthode permettant de tester l'intersection de triangles tridimensionnels n'utilisant que des prédicats de degré 3. L'implémentation obtenue se compare très favorablement aux méthodes déjà existantes à la fois en termes de robustesse et de temps de calcul.


 


Marc Glisse (lundi 14, 17h-17h30) 
        


Cost-optimal quadtrees for ray shooting

Dans le rendu de scènes 3D, la routine la plus appelée est sans doute le lancer de rayon. De nombreuses études théoriques ont été faites permettant de minimiser le coût de ce lancer dans le cas le pire. Dans [Cost prediction for ray shooting, ACM SCG 2002], les auteurs introduisent une mesure sur le temps moyen du lancer de rayon dans un octree. Nous essayons ici de construire un octree optimal (à une constante près) vis-à-vis de cette mesure. Ces travaux incluent un algorithme dynamique de construction d'octrees, un critère général de terminaison pour la subdivision des feuilles des octrees, et un certain nombre de considérations sur le rééquilibrage des octrees.


 


Xavier Goaoc (lundi 14, 17h30-18h) 
       


Sur le nombre de droites tangentes à quatre polyèdres

We prove that the number of lines tangent to four possibly intersecting polytopes in R3 with a total of n edges is either Theta(n2) or infinite which improves the previously known O(n4) trivial bound. More generally, we show that a set of k polytopes with a total of n edges has either infinitely many or Theta(n2 k2) lines, possibly occluded, tangent to four of these polytopes. When there are infinitely many tangents, then they form O(n2 k2) connected components.


 


Steve Oudot (mardi 15, 16h30-17h) 
        


Raffinage de maillages et échantillonnage de surfaces

L'utilisation du calcul numérique pour la résolution d'équations aux dérivées partielles sur un domaine compact nécessite le support d'un maillage de ce domaine. Nous présentons ici un nouvel algorithme de raffinage de maillages de surfaces, basé sur la technique de Ruppert et sur la triangulation de Delaunay volumique. Nous donnons des garanties théoriques quant à la terminaison de l'algorithme et à la qualité des résultats qu'il produit. Ces garanties sont confrontées aux résultats expérimentaux obtenus par la version implementée en C++ avec la bibliothèque de calcul géométrique CGAL.

Par ailleurs, nous utilisons notre algorithme de raffinage comme échantillonneur de surfaces implicites et évaluons ses performances en tant que tel. Ceci nous amène à considérer la valeur d'un échantillon non plus à travers ses qualités intrinsèques, mais plutôt en fonction des garanties qu'il donne sur l'échantillon final.


 


Pierre Alliez (mardi 15, 17h-17h30) 
         


Compression de maillages surfaciques et volumiques

Le développement fulgurant des réseaux et de l'Internet permet l'échange d'objets géométriques complexes. Dans ce contexte les maillages jouent un rôle prépondérant, qu'ils soient surfaciques ou volumiques. Dans cet exposé, je passerai en revue les derniers travaux effectués en compression, dans le prolongement d'un papier fondateur de Touma et Gotsman. En particulier, j'expliquerai notre démarche pour aboutir à une approche unifiée pour les maillages surfaciques triangulaires, quadrangulaires, polygonaux et plus récemment tétraédriques, voire hexaédriques. Pour le codage de la connectivité les performances de cette approche s'expliquent en montrant le lien avec une énumération de graphes calculée par Tutte. Une ``feuille de route'' détaillera les travaux en cours et futurs.


 


Guillaume Allègre (mardi 15, 17h30-18h) 
         


Optimisation graphique d'un arrangement de droites

Dans le contexte des représentations planaires d'un arrangement de droites, nous avons étudié les critères numériques permettant d'évaluer la lisibilité géométrique d'une représentation.

Nous détaillerons un algorithme utilisant le critère d'allongement minimal pour optimiser la représentation d'un arrangement (de combinatoire fixée), et présenterons les résultats obtenus, de manière interactive ou automatique, par le logiciel, ainsi que certaines situations de blocage mises à jour.


 


Julia Flötotto (mardi 15, 18h15-18h45) 
          


A coordinate system on a surface: definition, properties and applications

Coordinate systems associated to a finite set of sample points have been extensively studied, especially in the context of interpolation of multivariate scattered data. Notably, Sibson proposed the so-called natural neighbor coordinates that are defined from the Voronoi diagram of the sample points. A drawback of those coordinate systems is that their definition domain is restricted to the convex hull of the sample points. This makes them difficult to use when the sample points belong to a surface. To overcome this difficulty, we propose a new system of coordinates. Given a closed surface S, i.e. a (d-1)-manifold of Rd, the coordinate system is defined everywhere on the surface, is continuous, and is local even if the sampling density is finite. Moreover, it is inherently (d-1)-dimensional while the previous systems are d-dimensional. No assumption is made about the ordering, the connectivity or topology of the sample points nor of the surface. A prototype for computing the coordinate function has been implemented based on the CGAL library. We present some basic issues concerning the implementation. Furthermore, we develop some applications.


 


David Cohen-Steiner (mardi 15, 18h45-19h15) 
           


Estimation des courbures principales via le cycle normal

In this talk, we address the problem of estimating the curvature of a surface from a polyhedral approximation of it. We use the theory of normal cycles from differential geometry to define curvature tensors for a general class of surfaces, including smooth and polyhedral ones. More precisely, we associate with each region of a surface a tensor which in the smooth case is the average of the curvature tensor over this region. The curvature tensor of a polyhedral approximation of a smooth surface then provides an estimator of the one of the smooth surface. Our main result is the convergence of our estimator when the polyhedral approximation is chosen to be the Delaunay triangulation restricted to the surface, with a mild local uniformity condition on the sampling. To the best of our knowledge, no such convergence result has been obtained in the past.


 


Sylvain Pion (mercredi 15, 9h-9h30) 
  


Bornes de separation constructives pour des rationnels k-aires en entree

La technique des bornes de separation constructives permet de determiner a quelle precision il est necessaire de calculer numeriquement une expression, afin de prouver si elle vaut exactement zero ou non. Les bibliotheques CORE et LEDA proposent des types de nombres incluant ces methodes, qui permettent de determiner de maniere exacte le signe d'expressions basees sur des entiers, et autorisant les operations arithmetiques +, -, *, / et racines carres, (la methode s'etend aux racines p-iemes et aux nombres algebriques definis par leur polynome).

Je presenterai brievement les techniques de bornes de separation, et notamment la methode BFMSS et l'implantation dans la bibliotheque CORE. Puis je parlerai de nos travaux recents, qui concernent une approche generale permettant d'obtenir des bornes efficaces en presence de nombres flottants ou decimaux en entree. Cette methode permet, en quelque sorte, de se ramener au cas des entrees entieres, pour lesquelles les methodes actuelles comme BFMSS sont generalement nettement meilleures, et permet donc de determiner plus rapidement le signe d'une expression.

Travail en collaboration avec Chee Yap.


 


Geoffroy Lauvaux (mercredi 15, 12h-12h30) 
  


Une méthode rapide de quantification des volumes cachés : application à la stratification

Nous proposons un algorithme destiné à quantifier les volumes cachés générés par un polyhèdre et une source mono-directionnelle ou ponctuelle. Les principales particularités de cet algorithme sont :
- la discrétisation du volume résultat
- son indépendance vis-à-vis de la complexité de l'ombre du polyhèdre projetée sur lui-même
- sa rapidité O(n), renforcée par la possibilité d'employer du hardware très courant propre à ce genre de calculs (GPU)
- la possibilité de travailler sur des strates du polyhèdre (partie du polyhèdre délimitée par deux plans parallèles)
Nous proposerons enfin son application à un procédé de prototypage rapide, Stratoconception(R).


 


Malvika Rao (mercredi 15, 16h30-17h) 
  


A randomized approach to robot localization

We consider the problem of localizing a mobile robot in a self-similar environment modeled by a simple polygon P. The robot is placed at an unknown location inside P. However, it has a map of P and from its initial location can sense its environment, thereby computing a set of visible vertices and edges that make up the visibility polygon of its location. Since the environment may contain self-similarities between separate portions, the same visibility polygon may correspond to several different locations. Therefore the robot must travel around its environment and collect additional sensory data in order to deduce its exact location. The problem of robot localization with minimum travel in a self-similar environment has been shown to be NP-hard by Dudek, Romanik, and Whitesides in their paper, ``Localizing a Robot with Minimum Travel'', SIAM Journal on Computing, 1998.

Our work attempts to develop an approximation algorithm for the problem of robot localization in a self-similar environment using a randomized approach.


 


Eric Colin de Verdière (mercredi 15, 17h-17h30) 
   


Système de lacets optimal sur une surface orientable

Toute surface compacte orientable sans bord est, à homéomorphisme près, une sphère ou un g-tore (accolement de g tores, pour un g>0). Un système (fondamental) de lacets d'un g-tore est un ensemble de lacets simples ayant un point commun v0, deux à deux disjoints sauf en v0, tel que le découpage de la surface selon ces lacets donne un disque topologique.

On sait calculer des systèmes de lacets d'une surface, ce qui est utile dans plusieurs applications (paramétrisation, maillage, plaquage de textures) ; mais il est souvent souhaitable d'avoir des lacets aussi courts que possible. Dans un cadre où les lacets sont tracés sur le graphe sommets-arêtes d'une surface triangulée, nous présentons un algorithme polynomial qui calcule un système de longueur minimale parmi tous les systèmes d'une classe d'homotopie donnée.

Travail en collaboration avec Francis Lazarus.


 


Nicolas Szafran (mercredi 15, 17h30-18h)  
    


Chemins et boucles géodésiques sur des polyèdres

Cet exposé présente une application du calcul de plus courts chemins (sur des surfaces triangulées) au calcul de boucle géodésique, cette application ayant été motivée initialement par un problème de modélisation de fibres du myocarde.

Dans un premier temps, des rappels sont faits sur le calcul de chemins géodésiques sur des polyèdres et surfaces triangulées.

Ensuite l'algorithme de calcul de boucle géodésique sur des polyèdres est présenté en détail et illustré par quelques exemples.

 


Francis Lazarus et Frank Hetroy (mercredi 15, 18h20-19h)  
     


Graphe des contours d'un polyèdre valué

Étant donné un polyèdre triangulé (i.e. une variété simpliciale) P et une fonction numérique f affine par morceaux sur P, on s'intéresse au graphe des contours de f sur P, c.-à-.d. au quotient de P par la relation x ~ y ssi x et y appartiennent à une même isoligne de f. Dans un premier temps nous ferons un état de l'art sur le traitement de ce graphe dans la communauté géométrie algorithmique. Dans une deuxième partie nous présenterons de manière originale un algorithme proposé par Carr, Snoeyink et Axen en 2000 en y apportant quelques extensions.



Mahmoud Melkemi (jeudi 16, 16h30-17h) 
      


Graphes moléculaires : une généralisation de la triangulation de Delaunay

La triangulation de Delaunay utilise un élément structurant de type disque. Ainsi, elle permet de déterminer les disques vides. Nous proposons une généralisation en utilisant comme élément structurant une région connexe ayant une forme quelconque.



Frédéric Jourdan (jeudi 16, 17h-17h30) 
       


Constructions à la règle avec l'algèbre de Grassmann-Cayley

On dispose avec l'algèbre de Grassmann-Cayley d'un formalisme algébrique permettant d'exprimer de manière compacte et synthétique les propriétés géométriques de configurations de variétés linéaires projectives (points, droites, plans...). On peut ainsi transcrire algébriquement toute construction à la règle seule, et réaliser par ce moyen diverses constructions classiques, entre autres la construction point par point d'une quadrique projective.



François Gannaz (jeudi 16, 17h30-18h) 
        


Quelques algorithmes d'approximation géométrique pour des espaces non-euclidiens

Pour de nombreux problèmes de géométrie algorithmique, il existe des algorithmes fournissant des solutions approchées. L'approximation de normes est une technique permettant de remplacer une norme coûteuse en termes de calculs par une norme plus simple. Les processus de construction d'une solution exacte pour cette nouvelle norme deviennent alors des algorithmes d'approximation pour la norme initiale. L'erreur commise peut être mesurée en termes de distance de Hausdorff entre les boules unités duales. On s'intéressera particulièrement aux espaces munis d'une métrique non-euclidienne.



Fernand Meyer (jeudi 16, 18h15-18h45) 
       


Minimal forests and paths algebra

The watershed transform is at the heart of morphological segmentation: the contours appear as grey tone or colour transitions in the image to segment and as watershed lines in its gradient image. Considering this gradient image as a topographic surface, the watershed may be constructed by flooding: the relief is flooded from a set of sources and each pixel is attributed to the source which flooded it. The present studies the resulting tessellation, given a set of sources.

We have shown in the past that this tessellation is a minimum spanning forest of the neighbourhood graph in which each node represents a catchment basin and each edge a pass point between neighbouring basins weighted by its altitude. Each tree of the forest is rooted in a source.

In this talk we characterise this tessellation as a Voronoi tessellation of the sources for a lexicographic distance. We define two internal laws for this distance, an ``addition'' and a ``multiplication'', giving to the lexicographic distances the structure of a dioid. Using the paths algebra introduced by Gondran and Minoux, we derive efficient algorithms for interactive segmentation.



André Lieutier (jeudi 16, 18h45-19h15) 
        


Quelques sous-ensembles sympathiques de l'axe médian

La preuve (récente) de l'équivalence d'homotopie d'un ouvert borné de Rn avec son axe médian introduit de nouveaux outils pour l'étude des propriétés de l'axe médian, et ce dans un cadre très général (pas d'hypothèse sur la régularité de la frontière et uniformité des concepts par rapport à la dimension de l'espace).

Ces outils conduisent à différentes façons de structurer l'axe médian en composantes remarquables.

Certaines composantes ont par exemple de meilleures propriétés de stabilité que l'axe médian lui-même, et se prêtent donc mieux au calcul, notamment à partir de données partielles.

D'autres composantes semblent capturer la ``morphologie'' de l'ouvert et quelques conjectures ou questions ouvertes seront formulées.


Pour toute question : jga02@loria.fr