Journées de Géométrie Algorithmique 2003

VVF de Giens -- 15-19 octobre 2003



Résumés des cours

Pseudotriangulations - a survey and recent results.
Günter Rote
Pseudotriangulations have recently emerged in different areas within computational and discrete geometry and in combinatorics: visibility, kinetic data structures, mechanisms and motions, rigid frameworks and stresses, non-crossing trees and other Catalan structures, the secondary polytope and the associahedron, the reflex-free hull, and three-dimensional polyhedral surfaces.
I will show some basic properties of pseudotriangulations, give a survey of various connections and applications, and mention some recent results and open questions.

Méthodes algébriques pour les prédicats géométriques
Ioannis Emiris
Une tendance importante aujourd'hui en géométrie algorithmique concerne l'étude des problèmes non-linéaires comme, par exemple, les arrangements des courbes et des surfaces et les diagrammes de Voronoï des objets courbes. Les prédicats géométriques, donc, qui ne faisaient pas souvent l'objet d'une étude algorithmique, constituent maintenant un point critique dans la conception et l'implémentation d'un algorithme géométrique. Ce cours présente certains outils algèbriques qui ont été employés ou peuvent être employés pour traiter de manière exacte et efficace des prédicats géométriques.
Notre boite à outils contient les séquences de Sturm et la règle de Descartes, afin d'étudier les nombres algèbriques réels définis par des polynomes en une variable. Ces techniques sont souvent complémentées par le résultant d'un système polynomial, une notion qui sera discutée aussi. De plus, le résultant sert pour passer dans le cas multivarié, puisque elle offre une approche pour obtenir la table de multiplication. Nous allons illustrer ces méthodes, et surtout celle des séquences de Sturm, par des applications géométriques qui aboutissent à des polynomes de petit degré. De l'autre coté, des points blocants dans l'utilisation de ces méthodes vont être traités, tels que le calcul de points d'isolation et le traitement de cas dégénérés.
Petite bibliographie:
C. Yap, Fundamental Problems of Algorithmic Algebra, Oxford Univ. Press, 2000.
I. Emiris et E. Tsigaridas, Methods to compare real roots of polynomials of small degree, Report ECG-TR-242200-01, 2003.


Singularités
Pierre Pansu
Tout ensemble fermé peut être défini par une équation indéfiniment dérivable. Néanmoins, certains invariants (e.g. les entropies) d'un ensemble peuvent être estimés en fonction des derivées de l'équation (Yomdin 1983). La méthode repose sur la théorie des ensembles semi-algébriques (triangulabilité, estimation des nombres de Betti) et la géométrie intégrale.

Enjeux géométriques en biologie structurale
Bernard Maigret


Échantillonage et problèmes géométriques en ligne
Herve Brönnimann
Les flux de données s'annoncent comme un paradigme algorithmique nouveau et très intéresssant dans le contexte des réseaux. Les données en flux peuvent provenir de sources variées comme réseaux IP, téléphonie portable, capteurs (MEMS, surveillances météorologique et environnementale, etc.) et données satellites, internet, ou même jeux de données stockées sur disques (mais trop gros pour être chargés en un seul morceau). Le défi est d'adapter les algorithmes classiques à ce cadre où les données, une fois vues, doivent être jetées: en théorie, la mémoire utilisée doit être constante ou au plus logarithmique en la taille du flux. En pratique elle est limitée par la mémoire disponible (le flux, lui, n'est pas limité). Je présenterai des algorithmes et structures de données pour fouiller ces données et maintenir des descriptifs adéquats (quantiles et histogrammes, échantillons, synopses, enveloppe convexe et autres descriptions géométriques).

Compression de modèles géométriques 3D
Pierre Alliez, Olivier Devillers
Le développement rapide des réseaux et de l'Internet permet l'échange d'objets géométriques complexes, à condition d'en élaborer des représentations concises et adaptées à la transmission. Dans ce cours nous passerons en revue les principaux travaux effectués en compression de modèles géométriques. La première partie du cours présente les motivations et plusieurs techniques de codage de maillages surfaciques, à la fois mono-résolution et progressives. La seconde partie concerne les techniques de compression spectrale et ondelette de modèles surfaciques, le codage de modèles volumiques ainsi que les codeurs spécialisés aux iso-surfaces et aux objets en mouvement. On mentionnera également les méthodes résistant à la transmission avec pertes, ainsi que celles fonctionnant en mémoire externe pour traiter les masses de données géométriques.

Résumés des exposés

Droites transversales à des segments dans R3
Sylvain Lazard
Nous décrivons la structure des composantes connexes de l'ensemble des droites transversales à n segments dans R3. Nous montrons que n <= 3 segments quelconques dane R3 admettent 0, 1, ..., n ou un nombre infini de droites transversales. De plus, dans le cas ou les droites transversales sont en nombre infini, elles forment de 1 à n composantes connexes de droites.

Décompositions optimales de surfaces en pantalons.
Francis Lazarus
On s'intéresse au calcul d'un cycle de longueur minimale dans la classe d'homotopie libre d'un cycle simple tracé sur une surface combinatoire orientable. Nous montrons que ce calcul peut être obtenu en temps polynomial et que le cycle minimal peut être choisi lui-même simple. Nous utilisons pour cela des ensembles maximaux de cycles simples, disjoints et deux à deux non-homotopes, aussi appelés "décompositions en pantalons".

Quelques proprietes de $M_{\lambda}$, un sous ensemble de l'axe Median.
André Lieutier
Un point x est dans l'axe Median d'un ouvert si l'ensemble B(x) des points de la frontière qui minimisent la distance à x contient au moins deux elements. M_{\lambda}, sous-ensemble de l'axe Median, est constitué des points pour lesquels le rayon de la plus petite sphère contenant B(x) est supérieur ou égal a \lambda.
On donne ici quelques propriétés de M_{\lambda}, concernant notamment son type d'homotopie et sa stabilité par rapport aux perturbations de la frontière de l'ouvert. L'axe Médian, ne peut être connu (approche) qu'au prix d'une connaissance (une approximation) de la courbure de la frontière de l'ouvert. En revanche, dans le cas, plus vraisemblable en pratique, où l'ouvert est connu avec une précision finie en distance de Hausdorff (résultat de mesures physiques comme par exemple un échantillon de points mesures sur sa frontiere ou résultat d'un calcul approche), M_{\lambda} garde un sens.

Algorithmes de construction de la frontière de classification pour la règle du plus proche voisin.
Stefan Langerman
Etant donné un ensemble de n points rouges et un ensemble de n points bleus, la règle du plus proche voisin attribue a un nouveau point la couleur du point qui lui est le plus proche. Cette règle partitionne implicitement l'espace en deux régions, une rouge et une bleue, séparées par une frontière de classification.
Je présenterai des algorithmes pour construire ces frontières de classification pour des ensembles de points sur une ligne et dans le plan. Les deux algorithmes fonctionnent en un temps O(n log k), ou k est la complexité de la frontiere de décision. Ce temps est optimal pour les paramètres n et k.
(Collaboration avec D. Bremner, E. D. Demaine, J. Erickson, J. Iacono, P. Morin, et G. T. Toussaint).

Autour de la complexité de points échantillonnant une surface
Dominique Attali (1h)
Il est bien connu que la complexité de la triangulation de Delaunay de n points dans R^3 peut être Omega(n). Le cas de points échantillonnant une surface présente un intérêt pratique car de nombreuses méthodes de reconstruction de surface s'appuient sur la construction de la triangulation de Delaunay de points appartenant à une surface. Ce n'est que très récemment que des résultats nouveaux ont été obtenus concernant la complexité de Delaunay de points échantillonnant une surface. Ces résultats diffèrent par le type de surfaces considérés et les conditions d'échantillonnages de ces surfaces. Dans cet exposé, je passerai en revue quelques résultats récents. En particulier, je présenterai la borne en O(n sqrt(n) ) obtenu par Erickson et l'exemple qu'il a construit pour prouver que cette borne est effectivement atteinte (Erickson 2001, Erickson 2002). Je présenterai le résultat en O(n) obtenu dans le cas de surfaces polyédriques (Attali et Boissonnat 2002) et le résultat en O(n_log n) dans le cas de surfaces lisses génériques (Attali, Boissonnat et Lieutier 2003).

Estimation des Quantites Differentielles par Ajustement Polynomial des Jets Osculateurs
Marc Pouget
Cet expose concerne l'estimation locale des propriétes différentielles d'une variété lisse S --une courbe dans le plan ou une surface en 3D-- à partir d'un nuage de points échantillonnés sur S. La méthode consiste à ajuster la représentation locale de la variété par un jet, en interpolant ou approximant. Un jet est un developpement de Taylor tronque, et l'intérêt des jets est qu'ils codent toutes les quantites géométriques locales --telles que la normale, les courbures, les extrema de courbure. Avec l'utilisation des jets, le probleme d'estimation des quantités différentielles est placé dans le cadre plus général de l'interpolation/approximation multivariée, un sujet classique d'analyse numérique. Sur le plan théorique, nous donnons des résultats de convergence lorsque l'échantillonnage est raffiné. Pour les courbes et surfaces, ces résutats sont des estimations asymptotiques avec des vitesses de convergence fonction du degré du jet utilisé. Pour le cas des courbes, une majoration d'erreur est aussi fournie. A notre connaissance, ces résutats sont parmi les premiers fournissant des estimations précises pour les quantités différentielles d'ordre trois et plus. Sur le plan algorithmique, nous traitons le probleme d'interpolation/approximation avec des systemes de Vandermonde. Des résultats expérimentaux pour les surfaces de R3 sont analysés. Ces experimentations illustrent les résultats de convergence asymptotique, ainsi que la robustesse de la méthode sur des modèles de Computer Graphics.

Intersection de 2 quadriques : optimalité et problèmes ouverts.
Sylvain Lazard
Nous présentons des résultats théoriques et expérimentaux sur la taille coefficients apparaissant dans la paramétrisation de l'intersection de deux quadriques en fonction des algorithmes employés

Algorithme de balayage d'un arrangement de quadriques
Jean Pierre Tecourt
Dans cet exposé, on présentera un algorithme de balayage d'un arrangement de quadriques. On verra que l'on calcule en fait une décomposition verticale de l'arrangement et on en déduira un résultat de complexité. L'exposé sera centré sur les aspects algébriques rencontrés: comparaison de nombres algébriques, détection des événements...

Sur une Analyse des Formes Moléculaires basée sur le Complexe de Morse-Smale et la Fonction de Connolly
Frédéric Cazals
Le docking fait référence à l'ensemble des mécanismes intervenant lorsque deux ou plusieurs molécules forment un complexe moléculaire. Ces mécanismes font intervenir, outre la géométrie des molécules, leurs propriétés physico-chimiques. Dans le registre géométrique du docking, Connolly a proposé au milieu des années 80 un algorithme associant certains creux à certaines bosses des molécules impliquées. Par creux et bosses on entend plus précisément les extrema locaux de la fonction de Connolly qui se définit comme suit. Soit M une surface de R3 délimitant un volume X , et soit S une sphère centrée en un point p de S . La fonction de Connolly est définie comme l'angle solide associé à la portion de S contenue dans X .
Ce travail fait le lien entre l'algorithme de Connolly et la théorie de Morse, et plus précisément les fonction bivariées définies sur des surfaces de R3 . Les contributions sont de quatre ordres. Premièrement, on s'intéresse à la nature des points critiques de la fonction de Connolly pour des surfaces lisses. Deuxièmement, on décrit un algorithme efficace de calcul de la fonction de Connolly pour les surfaces triangulées. Troisièmement, en s'appuyant sur la théorie de Morse discrète, on introduit la notion de diagramme discret de Morse-Smale. Étant donnée une fonction de Morse ---ou de façon équivalente un champs de gradients, ce diagramme induit une partition de la surface en régions de flot homogène, et établit un lien entre certaines propriétés locales et globales ---des points critiques à la caractéristique d'Euler. On décrit également un algorithme de calcul de ce complexe en O(n\log n) . Des résultats expérimentaux sur plusieurs modèles concluent le travail.

Distances maximales et problèmes géométriques équivalents
Bernard Lacolle et François Gannaz
Nous présentons quelques perspectives pour la résolution approchée de certains problèmes de géométrie qui s'interprètent comme la maximisation de distances. Nous ferons un tour d'horizon des problèmes de ce type habituellement traités, en commençant par l'un des plus simples, celui du diamètre, puis en introduisant des problèmes un peu plus complexes comme des problèmes de classification. Un principe couramment utilisé dans la résolution approchée de tels problèmes consiste à considérer des problèmes linéaires associés à des projections sur des directions échantillonnant la boule unité de la métrique euclidienne. Les résultats nouveaux mis en perspectives ici font suite aux travaux de la thèse de F. Gannaz. Nous utiliserons le fait que le principe d'échantillonnage de la boule unité peut s'étendre à d'autres distances que la distance euclidienne, qu'il est relié au problème d'approximation des convexes et de décompositions de normes. Ceci nous permet de généraliser les approches existantes et de conclure à une certaine optimalité. Nous présenterons ensuite brièvement quelques perspectives d'amélioration algorithmique.

Décomposition de normes de diagrammes de Voronoï
François Gannaz
Les diagrammes de Voronoï de n points pour des distances non-euclidiennes sont mal connus en dimension d>=3. La borne classique sur leur complexité maximale en O(n^{d+epsilon}, epsilon>0, est sans doute loin de l'optimal pour beaucoup de distances. Récemment, (1) a montré que cette complexité pour des distances simpliciales sur R^d était en Theta(n^{\lceil d/2 \rceil} ). Depuis, (2) a prouvé une borne de Theta(n^2) sur la complexité maximale dans _R^3 muni d'une distance à jauge polytopiale.
Nous présenterons tout d'abord l'outil de la décomposition de normes et montrerons comment ce dernier nous permet de nous ramener à une norme polytopiale. Nous étendrons alors cette même borne aux diagrammes de Voronoï dans R^3 muni d'une norme quelconque.

(1) J.-D. Boissonnat and M. Sharir and B. Tagansky and M. Yvinec, "Voronoi Diagrams in Higher Dimensions Under Certain Polyhedra Distance Functions",_emph_Discrete Comput. Geom._, _textbf_14_, 1998, 485--519.
(2)_ Christian Icking and Lihong Ha, "A tight bound for the complexity of voronoi diagrams under polyhedral convex distance functions in 3D", Proceedings of the thirty-third annual ACM symposium on Theory of computing, 2001, 316--321.

Calculs géodésiques sur des surfaces triangulées.
Gabriel Peyré
Dans cet exposé, on va montrer diverses applications des calculs de distances sur des variétés 3D. Le but est de construire des algorithmes rapides et robustes pour manipuler de manière intrinsèque des surfaces.
1. Calculs sur des grilles orthogonales
- L'approche level set.
- L'algorithme Fast Marching.
- Application aux contours actifs.
2. Extension à une variété triangulée
- L'algorithme Fast Marching.
- Extraction de géodésiques.
- Calculs de diagrammes de Voronoi.
3. Remaillage géodésique par propagation de fronts
- Distribution des points.
- Remaillage adaptatif.
4. Interpolation géodésique
- L'interpolation par voisins naturels.
- Extension aux surfaces.
- Aplatissement de surface par multidimensionnal scaling.
- Interpolation géodésique de l'aplatissement.
5. Segmentation de surface
- Distribution des points de base.
- Calcul des régions de Voronoi.
- Segmentation de Voronoi centroïdale.
- Extension de l'algorithme de Lloyd à des surfaces.


Diagrammes Ellipsoïdaux : application à la détection des structures à partir d'un ensemble de points 3D non organisé.
Sébastien Bougleux
Les diagrammes ellipsoïdaux sont des diagrammes affines définis en utilisant une distance paramétrique dont la boule unité est une boule ellipsoïdale. Les paramètres qui interviennent dans cette distance contrôlent l'élongation et l'orientation de la boule ellipso_dale associée. Basé sur ces diagrammes et leurs duaux, nous proposons le concept des alpha-fomes ellipso_dales qui est une extension du concept des alpha-formes permettant de détecter des structures dans une direction donnée. L'expérimentation de ce model de reconstruction s'avère robuste pour des ensembles de points de faible densité ou des ensembles de points qui proviennent d'un milieu perturbé.

Approximation de surfaces - deuxième étape : à propos des r-échantillons
Steve Oudot
Note : travail effectué en collaboration avec Jean-Daniel Boissonnat
Résumé : La notion d'r-échantillon, introduite par Amenta et Bern, est devenue un concept clé de la théorie de l'échantillonnage. Elle présente une propriété intéressante, qui est que si l'on a un r-échantillon X d'une surface lisse S, avec r assez petit, alors la triangulation de Delaunay de X restrein te à S est une bonne approximation de S, en termes de géométrie et de topologie. Ainsi, si l'on est capable de construire des r-échantillons, alors on est capable de construire de bonnes approximations des surfaces lisses.
Dans mon exposé j'introduirai un critère sur la triangulation de Delaunay restreinte qui garantit qu'un échantillon X est bien un r-échantillon d'une certaine surface S. Ce critère est facile à vérifier puisqu'il se ramène à contrôler les rayons d'un ensemble fini de sphères. Il peut donc être aisément utilisé par un algorithme. En guise d'applications, je présenterai deux algorithmes, l'un de vérification d'échantillons, l'autre d'échantillonnage de surfaces. Ce dernier, basé sur la technique de raffinage de Delaunay, n'a besoin de connaître la surface qu'en un nombre fini de points, ce qui le rend intéressant pour le probing.

Ondelettes géométriques, extension à des surfaces
Gabriel Peyré
Dans cet exposé, on va présenter brièvement la théorie des ondelettes classiques, en insistant sur les résultats d'optimalités sur des images à variations bornées, mais aussi les faiblesses en présence de régularité. Pour contourner ces problèmes, des ondelettes exploitant la régularité géométrique des images ont été proposées récemment. Enfin, on abordera la question de la généralisation de telles ondelettes à des surfaces.
1. La théorie classique des ondelettes
- Décomposition dans une BON et analyses multiresolutions.
- L'algorithme rapide.
- Compression d'images : optimalité, oui mais ...
2. Ondelettes géométriques
- Philosophie des bandelettes.
- Détection du flot.
- Segmentation et codage des coefficients.
3. Ondelettes sur des surfaces
- Maillage semi-régulier.
- Construction par lifting : force et faiblesses.
- Ondelettes surfaciques : vision purement algorithmique.
- Une autre vision : Décomposition du domaine de paramétrisation.


Un modèle hybride pour la création d'objets complexes en 3D.
Rémi Allègre
Ce travail s'inscrit dans le cadre de la modélisation géométrique de scènes complexes réalistes. La diversité des modèles existants a conduit à développer des approches multi-représentation afin de tirer parti de leurs propriétés complémentaires. Nous proposons un modèle hiérarchique permettant de faire interagir des maillages polygonaux et des surfaces implicites de façon cohérente, en bénéficiant de la formulation volumique des surfaces implicites pour les opérations de mélange et de combinaison booléenne, et de la formulation surfacique des maillages pour les opérations de déformation et la visualisation interactive. Un opérateur est appliqué dans la représentation la plus appropriée, en utilisant un mécanisme de conversion à la volée pour passer d'un modèle à un autre. L'ensemble du processus d'évaluation est automatique. Notre approche permet de construire aisément et de façon intuitive des objets difficiles à représenter dans les systèmes de modélisation conventionnels. Ce modèle est ouvert et pourra à terme gérer des niveaux de détails et intégrer de nouvelles représentations ainsi que des outils d'animation.

Mariette Yvinec
Last modified: Thu Oct 9 08:48:45 MEST 2003