Résumés des séminaires PRISME

Retour à la liste des séminaires Prisme

Retour à la liste des séminaires Prisme

   Maillages surfaciques et mobiles

La première partie de ce séminaire présente une méthode indirecte de maillage de surfaces paramétrées qui respecte une carte de tailles spécifiées. Cette carte définit un champ de métriques dans l'espace tridimensionnel, qui est ensuite induit dans le domaine des paramètres. Un maillage est généré en utilisant par exemple une approche combinée frontale-Delaunay. Divers exemples d'applications seront présentés. La deuxième partie décrit un schéma itératif de maillage d'un domaine plan à frontières mobiles, permettant la simulation de procédés mécaniques où un outil rigide déforme une pièce plastique endommageable. À chaque itération, un calcul détermine la nouvelle géométrie de la pièce en fonction des contraintes mécaniques, des contacts avec l'outil et des éléments endommagés. Une carte de tailles assurant le contrôle des erreurs géométriques et physiques est définie sur ce nouveau domaine, et un maillage adapté est généré.

Retour à la liste des séminaires Prisme

   Maillages gouvernes de surfaces discretes. Application a la simulation numerique en mecanique des fluides.

Dans cette presentation, on montre comment construire des maillages adaptes aux calculs dans un contexte de simulation numerique. Les surfaces considerees sont definies par une triangulation initiale. En particulier, seront abordes les problemes de construction de metriques geometriques anisotropes a partir d'un estimateur d'erreur geometrique, ainsi que les aspects algorithmiques du remaillage de surfaces discretes. Des exemples de maillages adaptes seront choisis dans le domaine de la mecanique des fluides (compressibles ou incompressibles) pour la simulation de phenomenes stationnaires et instationnaires.

Retour à la liste des séminaires Prisme

   Schéma canonique optimal d'une surface orientable

Il est connu que toute surface compacte orientable sans bord est, à homéomorphisme près, une sphère, un tore, ou, plus généralement, un g-tore -- accolement de g tores -- pour un certain entier g. Savoir découper un g-tore (g>0) pour en faire un disque topologique est important, parce que cela permet de déterminer une paramétrisation de la surface ; les applications sous-jacentes sont le maillage, le plaquage de textures, ou le calcul explicite d'un homéomorphisme entre deux g-tores donnés. Cela peut être obtenu en découpant la surface le long de 2g lacets simples ayant un point commun v, deux à deux disjoints sauf en v, l'ordre des lacets autour de v étant bien particulier ; on obtient ainsi un 4g-gone dont les côtés sont identifiés deux à deux sur la surface. Un tel ensemble de lacets est un _système fondamental canonique_ (plus brièvement, système) de lacets ; cette représentation de la surface par un 4g-gone s'appelle un _schéma polygonal canonique_. On dispose d'algorithmes pour calculer un tel système sur une surface triangulée, mais ils ne tiennent pas compte de la géométrie de la surface, et les lacets obtenus sont d'aspect irrégulier et plus longs que nécessaire. Nous montrons que, parmi tous les systèmes (sur le graphe sommets-arêtes) homotopes à un système donné, il en existe un dont chaque lacet a une longueur minimale parmi les lacets simples de sa classe d'homotopie. Nous donnons un algorithme polynomial permettant de calculer un tel système optimal. La méthode employée consiste à optimiser itérativement le système en raccourcissant un lacet, les autres restant fixés. La démonstration repose sur une étude des croisements d'un système S avec un lacet homotope à l'un des lacets de S. Travail en collaboration avec Francis Lazarus (CNRS et Université de Poitiers).

Retour à la liste des séminaires Prisme

   Evolution of apparent contours of smooth surfaces

The contour generator of a smooth surface in three-space, under parallel or perspective projection, locally separates backward and forward facing regions on the surface. It consists of those points on the surface where the normal is perpendicular to the direction of projection. The apparent contour is the projection of the contour generator onto the image plane. The apparent contour and the contour generator are important visibility features of a smooth surface, e.g., in connection with visualization and non-photorealistic rendering. In computer vision, techniques have been developed for partial reconstruction of a surface from a sequence of apparent contours corresponding to a discrete set of nearby projection directions. Generically, the contour generator is a smooth curve consisting of several components. These components may merge or split when the projection direction changes. In this talk we review an algorithm for the computation of the contour generator of implicit surfaces, and describe generic evolutions of the apparent contour under varying directions of projection.

Retour à la liste des séminaires Prisme

   Approximating simple curves in the plane by skin curves

We present a method to approximate a simple, regular smooth curve in the plane by a skin curve. Skin curves and surfaces were introduced by Edelsbrunner, mainly for modeling large molecules in biological computing. They exhibit nice properties, like fast visualisation, tangent continuity and ease of construction and morphing. Our goal is to investigate to what extent these curves also yield suitable approximation algorithms. A skin curve is parametrized by a set of weigthed points (circles) and a shrink factor. If the shrink factor is equal to one, the curve is just the boundary of the region enclosed by the circles. If the shrink factor is less than one, the skin curve is tangent continuous, due to the appearance of hyperbolic patches connecting the circles. The talk starts with a brief review of some relevant parts of the theory of skin curves. I subsequently discuss what restrictions there are on the shrink factor, and finally derive a bound on the distance between the approximating skin curve and the input curve. I conclude with a discussion of positive and negative features of this approach.

Retour à la liste des séminaires Prisme

   Flow diagrams and some applications

Flow diagrams are a new diagram in Euclidean space induced by a set of weighted points. Basically there is a primal and a dual version of a flow diagram. The primal version resembles the power diagram and the dual version resembles the Delaunay diagram of the points. We used the flow diagram in three dimensions for surface reconstruction and for some experiments in structural biology.

Retour à la liste des séminaires Prisme

   Maillages et ondelettes. Application au codage vidéo

Dans le cadre du codage vidéo, afin d'obtenir une bonne compression, il est important d'avoir une bonne modélisation du mouvement présent au sein de la scène observée. Dans les schémas de codage normalisés, ce mouvement est en général simplement représenté par un mouvement translationnel par blocs. L'utilisation de maillages actifs afin de représenter le mouvement apparent permet alors d'obtenir une meilleure modélisation et donc d'espérer développer de nouveaux schémas de codage plus performant. Nous présentons alors dans cet exposé un nouveau schéma de codage vidéo de type "analyse-synthèse" basé sur l'utilisation de maillages actifs et d'ondelettes 3D (plus précisément 2D+t). La vidéo est représentée via deux champs d'information; mouvement (par l'intermédiaire du maillage actif) et textures des différents objets présents dans la scène. Afin de coder ces informations, un schéma de codage par ondelettes 3D a été développé permettant de proposer une représentation compacte et échelonnable offrant différents niveaux de scalabilité (spatiale, temporelle, SNR, débit). L'estimation du mouvement est réalisée par l'intermédiaire d'un schéma multi-résolution, hiérarchique et multi-grilles sur des maillages hiérarchiques. Le codage de cette information est par la suite réalisé par une ondelette 2D+t (ondelette sur maillage + dimension temporelle). Un codage par plans de bits avec une optimisation débit-distorsion est ensuite réalisé afin de coder cette information efficacement. Un coût de moins d'un bit par noeud peut alors être obtenu pour représenter l'information de mouvement pemettant ainsi d'obtenir de très bas débits. Le schéma obtenu permet alors d'obtenir des performances en compression comparables à l'état de l'art en codage vidéo (H26L), tout offrant une représentation scalable.

Retour à la liste des séminaires Prisme

Retour à la liste des séminaires Prisme

   Formaliser les enveloppes convexes

Les outils de démonstration sur ordinateur permettent de décrire formellement des langages de programmation et des programmes écrits dans ces langages, ainsi que les propriétés logiques vérifiées par les entrées et les sorties des programmes. En théorie, ceci permet donc de construire la spécification des programmes, puis de vérifier que ces programmes respectent cette spécification. On arrive ainsi à des programmes "théoriquement" sans fautes. En pratique, la modélisation du domaine d'application comporte souvent des difficultés, et les domaines d'application qui s'expriment bien avec les mathématiques usuelles se prêtent mieux à cet exercice, c'est le cas de la géométrique algorithmique. Nous avons étudié les modèles abstraits du calcul d'enveloppe convexe pour vérifier formellement la correction de plusieurs algorithmes de calcul d'enveloppe convexe. Notre étude s'est basée dans un premier temps sur les "axiomes" proposés par D. Knuth pour décrire les propriétés attendues du prédicat d'orientation pour permettre cette programmation. Ce travail nous a permis d'obtenir une première version de plusieurs algorithmes de calcul d'enveloppe convexe, mais qui ont le défaut ne marcher sans erreur que pour des configurations générales des entrées. Nous avons ensuite étudié l'approche proposée par Alliez, Devillers et Snoeyink pour réduire les problèmes dégénérés. Nous avons également démontré que cette approche était correcte, dans la mesure où elle permettait d'assurer la terminaison des algorithmes, même si le résultat du calcul n'est plus à proprement parler, une enveloppe convexe. L'ensemble de ces travaux ont été effectué en supposant des calculs absolument exacts. Nous pourrons également discuter ce point.

Retour à la liste des séminaires Prisme

   Adaptation de maillage - Representation hierarchique et optimisation

On étudiera quels avantages théoriques et pratiques on peut retirer de l'adaptation de maillage lorsque l'on veut approcher une fonction par son interpolation ou approximation sur un maillage. On mettra en évidence quelques liens entre représentation hiérarchique et pré-conditionneur multiniveau pour l'optimisation.

Retour à la liste des séminaires Prisme

    Construction optimale de fonctions de Morse discretes

La theorie de Morse s'est revelee un outil puissant
de topologie algorithmique. R. Forman a introduit une
version discrete de cette theorie. Cette
construction, qui a deja fait ses preuves en
compression de modeles tri-dimensionnels et en
topologie, repose sur la construction de fonctions de
Morse discrete.

Retour à la liste des séminaires Prisme

  Détermination géométrique de chemins géodésiques

Un chemin géodésique entre deux points sur une surface de R³ est un
plus court chemin local. Ceci nous permet de caractériser un chemin
géodésique sur une surface polyédrique et nous conduit a développer
une méthode itérative pour les calculer exactement sur ce type de
surfaces.  A partir de cette méthode, nous proposons également de
calculer des chemins géodésiques sur des surfaces de subdivision,
limites d'une suite de réseaux générés par un schéma de
subdivision. Nous calculons une suite de chemins géodésiques sur les
surfaces polyédriques issues des réseaux de contrôle successifs. La
convergence de cette suite de chemins géodésiques est traitée et des
exemples sont présentés.

Retour à la liste des séminaires Prisme

    Medial Axis Homotopy

The main result presented here is \emph{the homotopy equivalence of
any bounded open subset of $\mathbb{R}^n$ with its medial axis}.
Because the medial axis is used in many fields of research in
Computational Geometry, it may be of interest to be able to rely on
general theoretical results on its nature, beyond the smooth case.
The aim of the presentation is to explain the general idea of the
proof and to detail some key steps.  Along the proof, one encounters
some subsets of the medial axis that may be of interest for surface
reconstruction, mathematical morphology or image analysis.

Retour à la liste des séminaires Prisme

"Interactive Geometry Remeshing"

We present an interactive technique for remeshing of irregular
geometry with a high level of control over the sampling distribution.

A first stage carries out a careful analysis of geometry through an
area-balanced atlas of parameterization and measurements of several
geometry-related quantities. Such an analysis outputs discrete 2D maps
of various quantities on which we perform signal processing machinery
in order to produce a control map -- a map which controls the sampling
density over the surface patch.

In the interactive stage of the remeshing process the control map is
modified with respect to the user requests and sampled at an
interactive rate using a one or two-dimensional error diffusion
algorithm commonly used for grey level image half-toning. A
constrained Delaunay triangulation combined with optional subdivision
and mesh optimization is then performed to produce the requested mesh.
As a result, the remeshing engine produces arbitrary complex meshes
with any of the following properties: uniformity, regularity,
semi-regularity, smooth gradation, or even sampling with respect to
any transfer function applied over curvature-related quantities.

Retour à la liste des séminaires Prisme

On a few Heilbronn-Type Problems

Arrangements of lines in the plane and algorithms for computing
extreme features of arrangements are a major topic in computational
geometry.  Theoretical bounds on the size of these features are also
of great interest.  Heilbronn's triangle problem is one of the famous
problems in discrete geometry: Given $n$ points in the unit square,
let $H (n)$ be the area of the minimum-area triangle defined by any 3
of the points, in the configuration of points that {\em maximizes\/}
this minimum; estimate $H (n)$.

We show a duality between extreme (small) face problems in line
arrangements (bounded by the unit square) and Heilbronn-type problems.
We obtain lower and upper combinatorial bounds (some are tight) for
some of these problems.

Retour à la liste des séminaires Prisme

Indexing Moving Points

I will describe several new external-memory data structures that support range queries for moving points. Specifically, for any set of linearly moving points in the plane, our data structures support queries of the following form: Given a rectangle $R$ and a real value $t$, report the points that lie inside $R$ at time $t$. We develop two basic data structures, a slow but stable structure based on partition trees, and a fast but volatile structure based on kinetic range trees. By combining these two structures, we obtain a tradeoff between the query time and the number of times the data structure needs to be updated due to the motion of the points. We also develop a structure where the query time depends monotonically on the difference between the time stamp $t$ and the current time. Finally, we develop an efficient data structure to answer approximate nearest-neighbor queries among moving points.

This is joint work with Panjak Agarwal and Lars Arge, presented at PODS 2000. See http://www.uiuc.edu/~jeffe/pubs/kindex.html for a copy of the paper.

Retour à la liste des séminaires Prisme

The hierarchical spatio-temporal Voronoi data structure

Les modèles de SIG actuels ne peuvent pas intégrer la dimension temporelle des données spatiales à cause du manque d'ajout et de suppression incrémentiels d'objets spatiaux. La structure de données de Voronoï, qui permet des mises à jour locales et séquentielles, peut résoudre ces problèmes. Ces mises à jour sont réalisées grâce à des commandes de construction qui sont composées d'actions atomiques (algorithmes géométriques pour l'ajout, la suppression et le déplacement d'objets spatiaux). La formalisation des commandes de construction mena au développement d'un language spatial formé d'un ensemble d'opérations atomiques sur les primitives spatiales (points et droites). Ceci a induit un nouveau modèle formel pour la représentation du changement spatio-temporel, où chaque mise à jour est identifiée par les nombres de régions de Voronoï nouvellement créées et inactivées. Ceci est utilisé pour l'extension du modèle vers la structure de données hiérarchique de Voronoï. Cette structure de données hiérarchique de Voronoï a un ordre temporel implicite des événements visible via les changements topologiques. Elle est équivalente à une structure événementielle qui peut gérer des données temporelles imprécises, des mises à jour cartographiques rétroactives, et la visualisation de l'évolution d'une carte.

Retour à la liste des séminaires Prisme

Etude de la représentation géométrique et texturelle de scènes 3D pour les services de visualisation dans un contexte télécommunicant

La réalité virtuelle représente aujourd'hui une technologie à part entière puisqu'elle autorise la simulation, la navigation et l'interaction avec un univers sensoriel synthétisé de toutes pièces. Les potentialités offertes par la réalité virtuelle ont été très bien perçues lorsque les ordinateurs graphiques ont été capables d'assurer un rendu des images à une cadence interactive. De plus, l'augmentation des capacités des machines coïncide aujourd'hui avec un développement vertigineux des réseaux, ce qui décuple littéralement le champ d'application de la réalité virtuelle. Plusieurs difficultés subsistent toutefois pour développer les services de télécommunications associés : le volume des données est considérable, l'affichage est coûteux en calculs et la nature des données nécessite une prise en compte spécifique dans le contexte client-serveur. Si l'on ajoute à cela l'inégalité des capacités des terminaux et la variabilité des réseaux, on obtient une synthèse du triple challenge de la thèse : le stockage, la transmission et la visualisation de scènes 3D complexes. On pourrait aussi résumer la problématique en endossant le temps d'une phrase, le rôle d'un opérateur de télécommunication : "quels que soient : le terminal, le volume de données à transmettre et le débit du réseau, l'utilisateur doit pouvoir visualiser à tout moment une image attractive".
Cet exposé relève le défi sous la forme de briques technologiques susceptibles de s'assembler pour composer un moteur de transmission et d'affichage de scènes 3D en réseau. Il propose des solutions correspondant à un schéma courant en codage de l'information audiovisuelle : simplification, approximation, et codage échelonnable. Il reste cependant une spécificité propre à la 3D : la visualisation. En effet, il est d'une part plus coûteux de projeter un polygone à l'écran plutôt que d'afficher un pixel, et d'autre part le point de vue hautement variable d'une caméra influence sensiblement la pertinence des données transmises. Sur le terminal, la visualisation dépendant du point de vue est assurée par une technique de reconstruction adaptative des surfaces fonctionnant par subdivision successive des régions d'intérêt et des silhouettes. Nous montrons qu'une telle reconstruction s'applique en cours de transmission et s'adapte aisément à la puissance graphique d'un terminal.

Retour à la liste des séminaires Prisme

Voronoi tessellation to model complex fluid

Retour à la liste des séminaires Prisme

Geometric Clustering Problems: An Overview.

Because of a wide range of applications, including facility location, information retrieval, data mining, molecular biology, and spatial data structures, various clustering problems have been studied in many different fields of computer science. This talk gives a a partial overview of geometric clustering algorithms, with emphasis on the work done in the computational geometry community. The talk will also mention a number of open problems in this area.

Retour à la liste des séminaires Prisme

Construction d'iso-surfaces sous contraintes de Delaunay. Application au calcul du squelette.

La visualisation d'images volumétriques passe par le calcul et l'affichage de surfaces particulières dans l'image comme les surfaces digitales ou les iso-surfaces.

Les iso-surfaces sont des surfaces triangulées de R3 approchant la frontière des objets présents dans une image. Elles présentent de bonnes propriétés topologiques et géométriques: ce sont des 2-variétés de R3; contrairement aux surfaces digitales, elles ne présentent pas d'aspect en marches d'escalier.

Dans cet exposé, nous montrons comment construire des iso-surfaces incluses dans la triangulation de Delaunay de leurs sommets. Cette construction se fait localement et reste valable même si le volume est anisotrope. Dans une deuxième partie, nous exploitons ce résultat pour pour déduire une représentation par squelette des objets. Nous proposons une méthode de simplification du squelette et une application au calcul de l'épaisseur.

Retour à la liste des séminaires Prisme

Reseaux probabilistes et planification de mouvement: un algorithme base sur la notion de visibilite

Les reseaux probabilistes ont ete introduits recemment en algorithmique de la planification de mouvement. On presentera une variante de cette technique basee sur la notion de visibilite: elle possede le double avantage de produire des reseaux de faible densite et de permettre un controle explicite de l'algorithme d'apprentissage. L'algorithme a ete integre dans la plateforme logicielle Move3D est sera illustre par des exemples issus de la robotique, de la CAO et de l'animation graphique.

Retour à la liste des séminaires Prisme

Maintenance of a Piercing Set for Intervals with Applications

joint work with Matthew Katz (Ben Gurion University, Israel) and Michael Segal (University of British Columbia, Canada)
We show how to efficiently maintain a minimum piercing set for a set $\S$ of intervals on the line, under insertions and deletions to/from $\S$. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time $O(c(\S) \log |\S|)$, where $c(\S)$ is the size of the new minimum piercing set. We also show how to maintain a piercing set for $\S$ of size at most $(1+\varepsilon)c(\S)$, for $0 < \varepsilon \le 1$, in $O (\frac{\log |\S|}{\varepsilon})$ amortized time per update. We then apply these results to obtain efficient solutions to the following three problems:
(i) the shooter location problem,
(ii) computing a minimum piercing set for arcs on a circle, and
(iii) dynamically maintaining a box cover for a $d$-dimensional point set.

Retour à la liste des séminaires Prisme

Structures de données dynamiques et localisation

Cette structure proposee par van Kreveld et Overmars organise les donnees 2d en deux couches, regies par le x-ordre et le y-ordre. La couche superieure est une arborescence equilibree, ayant pour feuilles des arborescences equilibrees appartenant a la deuxieme couche. Une telle strategie simplifie les problemes de mise a jour, par rapport aux k-d arborescences, lorsque l'on autorise l'insertion et la suppression de points. Les auteurs ont concu ces structures pour repondre aux problemes de recherche par plage (range searching), et les ont generalisees aux dimensions superieures. On peut relativement aisement les modifier pour les rendre interessantes dans les problemes de localisation dans les triangulations de Delaunay, dans le contexte dynamique amorti.

Retour à la liste des séminaires Prisme

Application de la géométrie algorithmique aux écoulements multiphasiques : La librairie GTS

La résolution numérique d'écoulements monophasiques remonte aux années cinquante avec les premiers calculs de portance de profils d'ailes pour l'industrie aéronautique. Depuis cette époque pionnière, un grand nombre de techniques ont été développées et étudiées de manière approfondie tant sur un plan théorique que pratique et sont maintenant bien établies.

La situation est beaucoup moins claire en ce qui concerne les écoulements multiphasiques. Ce type de problèmes nécessite la prise en compte des changements brutaux des paramètres physiques au passage de l'interface entre deux phases. D'autre part une fraction importante de l'énergie interne des systèmes considérés peut être d'origine surfacique (tension de surface par exemple), et une résolution précise de ces termes s'avère nécessaire.

Aprés un bref récapitulatif des principales méthodes utilisées à l'heure actuelle, je présenterai une approche où les interfaces sont représentées explicitement comme des surfaces tri-dimensionelles couplées avec la résolution volumique sous-jacente. Cette approche implique la résolution d'un certain nombre de problèmes géométriques traditionellement peu familiers pour les spécialistes de la mécanique des fluides numérique.

Le but de la librairie GTS (GNU Triangulated Surface Library) est d'implémenter un ensemble d'outils basés sur les résultats et algorithmes obtenus en géométrie algorithmique et utiles pour la résolution numérique de problèmes physiques divers impliquant la présence d'interfaces. J'insisterai plus particulièrement sur les problèmes de robustesse et de souplesse d'utilisation. L'ensemble des algorithmes actuellement implémentés dans GTS seront succintement présentés.

Retour à la liste des séminaires Prisme

Calcul géométrique sur des données incertaines

Je rappellerai pour quels types d'application il est nécessaire de prendre en compte l'incertitude sur les données numériques. Je présenterai des approches envisagées (théorie et implémentation).
On peut considérer, dans un premier temps, les problèmes suivants :
1) calcul d'une d'enveloppe convexe d'un ensemble de points en 2D (pour inscrire des méthodes existantes dans le contexte de la théorie des domaines). Ce problème est en fait constitué de deux problèmes :
quels sont les points qui sont sur l'E.C. ?
calculer une approximation du polygone convexe.
2) calcul de l'intersection/union/différence de polygones dans le plan. Dans ce cas, on peut envisager deux représentations :
- intervalles de polygones (intervalles pour l'ordre d'inclusion) (l'interêt est que l'on sait exactement quoi faire, le modèle est bien fermé)
- polygones d'intervalles (i.e. les sommets sont des rectangles) (l'intérêt est que c'est plus proche des représentations CAO, l'inconvénient est que le modèle n'est pas fermé (l'intersection de deux polygones est-elle encore un polygone ? ) si on ne sophistique pas un peu la notion de polygone).

Retour à la liste des séminaires Prisme

Partition de l'espace et analyse d'image en géographie

La détermination des aires d'influence des phénomènes géographiques, ainsi que la compréhension de leur dynamique, constituent un des objets majeurs de la recherche en géographie. Dans cette problématique, les méthodes les plus couramment utilisées relèvent de la modélisation (modèles gravitaires) et, plus récemment, de l'analyse d'image (partition de l'espace selon des polygones de Thiessen, algorithmes de squelettisation, "ligne de partage des eaux").

Les applications présentées traitent essentiellement de phénomènes démographiques et socio-économiques. Ici, les images à teintes de gris, analysées, ne sont pas des photographies aériennes ou satellitaires, mais des cartes, des couches d'information de SIG et des images issues de tableaux de données spatialisées. Les traitements d'images reposent sur des algorithmes de morphologie mathématique et portent sur :
- - l'analyse spatio-temporelle des bassins de population de l'aire marseillaise,
- - la hiérarchisation des centres de médecine spécialisée en région transfrontalière, la détermination de leur bassin de population respectif et leur emboîtement,
- - la segmentation tridimensionnelle appliquée à la délimitation de la polarisation urbaine.

Retour à la liste des séminaires Prisme

Multirésolution en Modélisation Géométrique et en Visualisation Scientifique

Introduction et tour d'horizon
suivi de
Nouvelles avancées

La visualisation scientifique comme la modélisation géométrique font apparaître une boucle de conception dans laquelle circule une grande masse de données, distribuées sur plusieurs sites, partagées entre divers acteurs, et définies sur des supports géométriques multiples.

Ces caractéristiques ont poussé les chercheurs à tenter d'adapter les méthodes d'analyse multirésolution basées sur la théorie des ondelettes, et appliquées avec succès en traitement du signal et en analyse d'images par exemple, à des types de données plus généraux, et définies sur des supports géométriques plus complexes.

Les méthodes d'analyse multirésolution permettent en effet de représenter une fonction à plusieurs niveaux de résolution, en stockant l'erreur entre deux niveaux successifs dans des coefficients dits de détail. Les ondelettes sont des fonctions de bases qui codent la différence entre les niveaux de résolution. Ce type de codage est donc adapté à la manipulation de grandes masses de données, à leur compression, à leur transmission progressive, à leur édition ou encore à leur visualisation à différents niveaux de résolution.

Le premier exposé portera sur les bases de l'analyse multirésolution, suivi d'un tour d'horizon de ses applications en modélisation géométrique et en visualisation scientifique.

Le second exposé débutera par la description des limites imposées par la théorie classique de l'analyse multirésolution. Un cadre mathématique moins restrictif sera ensuite développé. Ce cadre sera appliqué dans un premier temps à un problème de visualisation de données volumiques médicales. Il s'agira de permettre à l'utilisateur d'obtenir un compromis entre la régularité et la netteté des visualisations. Le même cadre sera par la suite utilisé pour permettre le traitement de données définies sur des triangulations irrégulières, planes ou sphériques. Deux algorithmes seront exposés, le premier concernant des données constantes par morceaux (une donnée par face), le second des données linéaires par morceaux (une donnée par sommet).
Georges-Pierre Bonneau

Retour à la liste des séminaires Prisme

De la géométrie algorithmique au calcul géométrique

Dans cette thèse, nous définissons des méthodes efficaces et génériques dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique, en se concentrant principalement sur l'évaluation exacte des prédicats géométriques. Nous avons exploré des méthodes basées sur l'arithmétique modulaire, ce qui nous a conduits à mettre au point des algorithmes simples et efficaces de reconstruction du signe dans cette représentation des nombres. Nous avons également mis au point de nouveaux types de filtres arithmétiques qui permettent d'accélérer le calcul des prédicats exacts, en contournant le coût des solutions traditionnelles basées sur des calculs multiprécision génériques. Nos méthodes sont basées sur l'utilisation de l'arithmétique d'intervalles, qui permet une utilisation souple et efficace, combinée à un outil de génération automatique de code des prédicats. Ces solutions sont maintenant disponibles dans la bibliothèque d'algorithmes géométriques CGAL.

Mots clés: géométrie algorithmique, robustesse, calcul exact, prédicat géométrique, filtre arithmétique, arithmétique d'intervalles, arithmétique modulaire, C++, CGAL.

In this thesis, we define efficient and generic methods in order to solve the robustness problems that arise in the field of computational geometry, and we concentrate especially on the exact evaluation of the geometric predicates. We investigated methods based on modular arithmetic, which led us to develop simple and efficient algorithms to reconstruct the sign in this number representation. We also developed new kinds of arithmetic filters, which allow to speed up the exact computation of predicates, working around the cost of traditionnal solutions based on generic multiprecision computations. Our methods are based on the use of interval arithmetic, which allows an efficient and simple use, combined to an automatic generation tool of the predicates code. These solutions are now available in the CGAL library of geometric algorithms.

Keywords: computational geometry, exact computation, robustness, geometric predicate, arithmetic filter, interval arithmetic, modular arithmetic, C++, CGAL.
Sylvain Pion

Retour à la liste des séminaires Prisme

Développement d'un outil de maillage 2D et 3D adapté à la modélisation géologique

Retour à la liste des séminaires Prisme

Contour Edge Based Polyhedron Visualization

We have studied a hidden-surface removal algorithm in object space for three-dimensional polyhedral surfaces based on contour edges. The polyhedral surfaces are restricted to orientable 2-manifolds and each edge is incident to two facets. For a given viewing direction, an edge is a contour edge if it is incident to a front-facing facet and a back-facing facet. Appel observed in 1967 that the visibility only changes at projected contour edges in the viewing plane. Our interest in the contour-edge approach is motivated with a promising analysis on the expected number of contour edges and their intersections in the projection for random orthogonal projections. We present solutions based on line-sweep algorithms in the viewing plane to compute the silhouette of a polyhedral surface and the hidden-surface removal in object space.

Retour à la liste des séminaires Prisme

Re-éclairage/Re-modélisation Virtuels et Rendu Interactif

Dans cet exposé, nous présentons deux projets de recherche, sur le re-éclairage et la re-modélisation virtuels, pour réalité augmentée, et sur un algorithme de rendu interactif par tracer de rayon. Pour le re-éclairage virtuel, nous reconstruisons la géométrie de la scène réelle par photogrammétrie, et ensuite nous utilisons un ensemble d'images du même point de vue, mais avec des éclairages différents, pour calculer une première estimation de la réflectance réelle. Nous utilisons un filtrage pour tenir compte des imprécisions dans la reconstruction. Cette réflectance approximative est ensuite utilisée pour initialiser un système de radiosité hiérarchique représentant l'éclairage réel de la scène, qui nous permet également de calculer rapidement l'éclairage indirect. L'éclairage direct est calculé directement par lancer de rayons. Grâce à une série d'optimisations que nous allons présenter, nous arrivons à modifier les conditions de lumière, ajouter des objets virtuels et d'enlever des objets réels, tout avec des temps de rendu quasi-interactifs, et en tenant compte des effets d'éclairage commun, c'est-à-dire des ombres et échanges lumineuses entre objets réels et virtuels. Pour le rendu interactif par lancer de rayons nous nous plaçons dans un contexte de mouvement du point de vue et des objets. Nous supposons que le système de rendu ne peut fournir qu'un très faible nombre d'échantillons par rapport au nombre de pixels de l'image. Pour donner à l'utilisateur une expérience interactive de rendu, nous stockons un certain nombre de points dans le ``render cache'' ; ces points sont ensuite re-projetés à chaque pas de temps sur l'image. Après une étape de correction des erreurs d'occultation, et un lissage, nous arrivons à présenter une image de assez bonne qualité à l'utilisateur. En parallèle, nous calculons une image de ``priorité'', qui permet l'identification des échantillons que nous demandons au système de rendu. Ce processus arrive à concilier les deux buts contradictoires, qui sont de bien étaler les points sur l'ensemble de l'écran, tout en échantillonnant les régions où ceci est nécessaire. Les résultats montre que pour des résolutions allant de 256x256 jusqu'à 320x320 nous arrivons à atteindre 10-15 images par seconde avec une qualité satisfaisante, en utilisant 1-4 processeurs R10000 pour le rendu. En utilisant un ordinateur de 60 processeurs, nous arrivons à avoir un rendu fluide pour le tracer de chemin, avec les effets de caustiques etc.

Retour à la liste des séminaires Prisme

Implicit Fairing of Irregular Meshes using Diffusion and Curvature Flow

In this talk, we will introduce new methods to rapidly remove rough features from irregularly triangulated data intended to portray a smooth surface. The main task is to remove undesirable noise and uneven edges while retaining desirable geometric features. The problem arises mainly when creating high-fidelity computer graphics objects using imperfectly-measured data from the real world.

Our approach involves three main novel features: an implicit integration method to achieve efficiency, stability, and large time-steps; a Laplacian operator to achieve a diffusion process that respects length scale; and finally, a robust curvature flow operator that achieves a smoothing of the shape itself, distinct from its parameterization. Additional features of the algorithm include automatic exact volume preservation, and hard and soft constraints on the positions of the points in the mesh.

We compare our method to previous operators and related algorithms, and prove that our curvature and Laplacian operators have several mathematically-desirable qualities that improve the appearance of the resulting surface. In consequence, the user can easily select the appropriate operator according to the desired fairing. Finally, we provide a series of examples to graphically and numerically demonstrate the quality of our results.

Joint work with M. Meyer, P. Schroeder, and A. H. Barr, to appear at Siggraph'99.
Mathieu Desbrun

Retour à la liste des séminaires Prisme

Calcul symbolique en Géométrie

Dans cet exposé, nous ferons un rapide tour d'horizon de méthodes et outils issus du calcul symbolique, pour le traitement d'objets géométriques. Nous nous intéresserons en particulier aux invariants des groupes classiques et à leur calcul effectif, à l'algèbre extérieure ou de Grassmann-Cayley, aux relations de Plücker, à l'espace des sphères et à certaines algèbres de Clifford.
Nous donnerons quelques illustrations de ces techniques en démonstration automatique, en robotique et en vision par ordinateur.
Nous conclurons sur des extensions possibles de cette approche, faisant intervenir à la fois des considérations formelles et numériques.
Bernard Mourrain et ses transparents (postscript gzippé)

Retour à la liste des séminaires Prisme

Rapidly-Exploring Random Trees and Kinodynamic Planning

A randomized approach to path planning will be introduced that is particularly suited for problems that have nonholonomic constraints, high degrees of freedom, and little structure that can be easily exploited (as in the case of Reeds-Shepp curves for car-like robots). The basis for this approach is the incremental construction of a tree that attempts to rapidly and uniformly explore the state space, offering benefits that are similar to those obtained by other successful randomized planning methods, but applies to a much broader class of problems. In each iteration the tree is expanded by applying control inputs that drive the system slightly toward randomly-selected points, as opposed to requiring point-to-point convergence. Issues will be discussed for applications to holonomic and nonholonomic planning; however, the most challenging and general set of path planning problems lie in the area of kinodynamic planning. By using a state space formulation, the kinodynamic planning problem is treated as a 2n-dimensional nonholonomic planning problem, derived from an n-dimensional configuration space. The state space serves the same role as the configuration space for standard path planning; however, existing randomized path planning techniques do not directly apply to this difficult class of problems. Although our method is not complete, it yields practical solutions to many problems, and its behavior is relatively simple to characterize. Some preliminary results will be discussed for an implementation that determines kinodynamic trajectories for automobiles, hovercrafts, and satellites in cluttered environments, resulting in state spaces of up to twelve dimensions.
Steven M. LaValle

Retour à la liste des séminaires Prisme

P2MESH: a collection of template classes for implementing FE and FV PDE solvers on 2-D unstructured grids

P2mesh is a software system which makes possible the implementation of numerical solvers for Partial Differential Equations (PDEs) using FE or FV methods on 2-D unstructured grids. It provides the application programmers with an easily extensible and computationally efficient environment which transparently manages the geometrical and topological information of the underlying mesh. The software system consists in a set of partially defined C++ template classes, which can be directly used by programmers to build mesh-based data structures.
CNR-IAN

Retour à la liste des séminaires Prisme

Calculs généraux d'occultation à l'aide de projections étendues

Realtime visualization of very complex scenes, often containing many millions of polygons, is still a challenging task for mid- and even high-range graphics workstations. To accelerate display, we present a new preprocessing method which calculates conservative, potentially visible geometry in the cells of a spatial subdivision. We introduce extended projection, a novel method to create extended occlusion maps by projecting appropriately chosen blockers onto a suitable projection plane. Unlike methods which project with respect to a single viewpoint, this approach encodes occlusion with respect to an entire cell and allows efficient detection of hidden objects. Using extended projection, the combined effect of multiple blockers on occlusion with respect to the cell is taken into account. Concave objects as well as complex objects built of many smaller primitives (such as trees) are also treated effectively. This is achieved by appropriately representing occlusions and combining these representations on successive projection planes. The cell structure containing the potentially visible sets is built adaptively and coded efficiently to reduce storage requirements. We treat moving objects by including motion volume visibility information in the potentially visible sets. We have implemented our algorithm and have run several examples including the model of a city which contains moving cars, and also a model of a forest. In both cases we achieve highly interactive display and significantly reduce the number of primitives sent to the graphics pipeline at each frame, compared to previous approaches.

Retour à la liste des séminaires Prisme

Métamorphoses tridimensionnelles : tour d'horizon et perspectives

Une métamorphose tridimensionnelle, souvent appelée ''morphing 3D'' en infographie, est le passage continu d'un objet à un autre.
Les métamorphoses 2D et 3D sont utilisées en animation, pour concevoir de nouvelles formes ou dans des processus de simulation de croissance. Comme il n'existe pas de solution intrinsèque au problème de métamorphose, l'intervention de l'utilisateur est déterminante dans les logiciels de métamorphose. De nombreuses méthodes de métamorphoses 2D et 3D ont été proposées ces dernières années. Nous nous intéressons ici aux métamorphoses tridimensionnelles et considérons plus particulièrement l'interaction avec l'utilisateur. Nous montrons comment les méthodes sont intimement liées à la représentation des objets à transformer.
Nous concluons en indiquant des stratégies pour de nouvelles méthodes de métamorphose.

Retour à la liste des séminaires Prisme

k-Nearest-Neighbours Gibbs Point Processes
Résumé et références

Retour à la liste des séminaires Prisme

 C++ Classes for 2-D Unstructured Mesh Programming

The main features of a set of C++ classes for 2-D mesh programming will be presented. The design of these classes seeks to achieve:
- simplification of mesh programming, of course
- code reuse across different applications
- separate compilability

These classes support programming with conforming triangular meshes in the plane or on manifold surfaces in space and collections of such meshes joined along piecewise linear boundaries, which we refer to as composite meshes.

Simple classes for the basic mesh objects, i.e. vertices, triangles, and line segments, are described, and a mesh class, which is an intelligent container class of three lists of these simple mesh objects. These classes are intended to be components in an object oriented approach to software for meshing applications. This context differentiates the roles of the mesh class and the simple mesh object classes. These latter are the carriers of geometric and of the applications data. They also define primitive functions which are used by the mesh container class and the mesh generation programs. We discuss appropriate primitives and program design.

Retour à la liste des séminaires Prisme

Delaunay-admissibilite en dimensions 2 et 3

Cette communication presente des methodes de redefinition a priori de champs de contraintes, representes en dimension 2 par un ensemble de segments, en dimension 3 par une triangulation surfacique. Le but est de produire un nouveau champ de contraintes qui soit fortement Delaunay-admissible (i.e. qui sera construit par toute triangulation de Delaunay, non necessairement unique, de l'enveloppe convexe du nuage de points auquel se rapporte la contrainte). Le probleme bidimensionnel est tout d'abord resolu, au moyen d'une classification conduisant a un algorithme convergent. Bien que la classification s'etende aux faces triangulaires, une propriete essentielle disparait en dimension 3, excluant une extrapolation simple de la methode. Neanmoins, un algorithme heuristique base sur des subdivisions de faces et des bascules d'aretes et gouverne par un estimateur geometrique est propose. Des exemples illustrent le propos, et une breve description de la methode convergente en cours de demonstration est donnee.

Retour à la liste des séminaires Prisme

 Reconstruction 3D en imagerie médicale nucléaire

L'exposé comporte deux parties:
Dans une première partie [1] on s'intéresse à la reconstruction volumique d'un objet à partir de ses projections acquises en géométrie conique. On présente les problèmes de calibration, manque de données, et rapport signal à bruit faible. On propose alors une approche régularisation dans un cadre semi-quadratique. On présente l'intérêt de la méthode sur des simulations puis sur des cas réels d'imagerie SPECT de la thyroïde.

Dans la deuxième partie [2] on se propose de segmenter l'image 3D à reconstruire à partie de la connaissance des projections acquises en géométrie conique. On propose une méthode baséee sur l'évolution de contours actifs déformables 3D. On propose plusieurs solutions pour l'évolution du contour. La méthode est d'abord validée sur des simulations puis sur données réelles SPECT du thorax.

[1]I. LAURETTE, J. DARCOURT, L. BLANC-FERAUD, P.-M. KOULIBALY, M. BARLAUD "Combined Constraints for Efficient Algebraic Regularized Methods in Fully 3D Reconstruction" Journal of Physics in Medicine and Biology April 1998
[2]ATTENUATION MAP SEGMENTATION WITHOUT RECONSTRUCTION USING A LEVEL SET METHOD IN NUCLEAR MEDICINE IMAGING Eric Debreuve; Michel Barlaud; Gilles Aubert; Jacques Darcourt ICIP 98 Chicago USA

Ces etudes font l'objet d'une collaboration entre l'Equipe Image du laboratoire I3S et Le Laboratoire de Biophysique et de Traitement d'image de l'UFR medecine (Theses de P.M. Koulibaly, I. Laurette et E. Debreuve)

Retour à la liste des séminaires Prisme

*** Modelisation a base topologique - combinatoire et plongement ***

Dans le cadre de la modelisation geometrique, on peut distinguer deux principaux aspects:
- L'aspect combinatoire decrit la subdivision des modeles en terme de primitives, ainsi que les relations d'adjacence/incidence entre ces primitives.
- Le plongement, qui regroupe la geometrie ainsi que les attributs attaches aux objects (couleur, texture, proprietes physiques modelisees...).

Depuis une vingtaine d'annees, differentes structures ont ete proposees pour definir des bases de donnees geometriques qui permettent de representer ces deux aspects. Parmi ces approches, on peut distinguer plusieurs grandes familles de modeleurs. Le modele CSG (Constructive Solid Geometry) decrit hierarchiquement les objects en terme d'operations appliquees a des primitives. Les approches dites d'enumeration spatiale decrivent les objets comme un assemblage structure' de cellules (comme par exemple les octrees et methodes derivees). L'approche B-Rep (Boundary Representation) modelise les objets par une discretisation de leur frontiere. Des representations de complexite croissantes ont ete proposees (Winged Edge, Half Edge, Radial Edge), ayant a la fois un domaine de representation de plus en plus large et une complexite' de structure de plus en plus grande.
Une derniere famille de modeles, dite modeles 'ordonnes' ou encore modeles 'cellulaires' trouve son origine dans la topologie algebrique, branche relativement recente des mathematiques. Ces modeles comptent par exemple les algebres d'aretes, les cartes combinatoires, le modele DCEL et les cartes generalisees. Nous nous interesserons plus particulierement a ces dernieres, qui permettent de representer les objets dits 'cellulaires quasi-varietes' en utilisant un seul type d'objet et un seul type de relations entre ces objets. On presentera egalement quelques modeles de plongement pour ces cartes generalisees, permettant de leur associer une geometrie et des attributs.

*** Modelisation volumique de 3-varietes : structures et algorithmes ***

Certains processus de simulation et de modelisation physique doivent permettre d'attacher des valeurs en tout point de l'espace, ces valeurs representant des grandeurs physiques telles la temperature, la pression, la porosite d'une roche ...

Un support geometrique va etre defini afin de representer les champs scalaires ou vectoriels associes aux valeurs modelisees. Ce support geometrique correspond a une subdivision de l'espace 3D. On va distinguer deux types d'approches, suivant que l'on souhaite subdiviser l'espace en grandes zones homogenes (par exemple des couches geologiques), ou avoir une discretisation de granularite plus fine permettant de modeliser les variations d'une propriete physique. Ces deux approches vont se traduire par deux methodologies differentes:
1) L'espace est subdivise en grands volumes, delimites par des surfaces. On represente alors deux niveaux de subdivisions, l'un correspondant aux relations entre les volumes ainsi defini, et l'autre correspondant a une discretisation des surfaces.
2) L'espace est subdivise en un ensemble de volumes elementaires. On represente alors l'ensemble des relations d'adjacence entre ces volumes.

Des algorithmes et structures de donnees associees sont etudies ici pour les deux approches, parmis lesquels la reconstruction des relations volumiques a partir d'un ensemble de surfaces, ainsi que differentes methodes de creation et d'edition de maillages.

Les approches classiques pour representer de telles subdivisions utilisent des structures de donnees complexes et nombreuses. Les algorithmes qui en decoulent sont difficiles a ecrire. Nous proposons de representer un objet base sur la notion des G-Cartes. Il en resulte que les structures de donnees sont plus simples. De plus, etant donne que la structure des G-Cartes est une structure mathematique, les algorithmes peuvent etre prouves mathematiquement.

Retour à la liste des séminaires Prisme

 Reconstruction géométrique de formes - Application à la géologie

Cette thèse s'articule autour de la reconstruction géométrique de formes. L'application visée est la modélisation et l'imagerie géologique.

L'objectif principal de cette thèse est de concevoir et réaliser un modeleur géologique tridimensionnel permettant de reconstruire des surfaces et des volumes géologiques à partir de données hétérogènes~: données ponctuelles sur des affleurements, portions de contours cartographiques, sondages, ou coupes interprétées. La géométrie 3D réalisée grâce à ce modeleur permet de visualiser les structures. Elle doit pouvoir servir aussi de base pour la réalisation de modèles quantitatifs et pour l'interprétation géodynamique.

Plusieurs méthodes ont été testées, basées sur des structures géométriques qui caractérisent la proximité des objets dans un modèle~:les diagrammes de Voronoï. Les objets naturels reconstruits par ces méthodes sont représentés par des volumes, sous forme d'union de volumes élémentaires (polyèdres de Voronoï), ou définis par les valeurs positives d'une fonction continue.

Stéphane Nullans

Retour à la liste des séminaires Prisme

 A Survey of Techniques for Batched Geometric Problems in External Memory

Data sets in large geometric applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this talk, we give a light survey the state of the art in the design and analysis of external memory algorithms for batched geometric problems. (No special background in algorithms is needed.) Applications include databases and geographic information systems (GIS).

The canonical external memory problem is sorting. We explain the fundamental lower bounds on the number of I/Os needed to sort and permute in external memory. We show how to sort optimally by use of the distribution and merging paradigms. External sorting arises indirectly in the solution of some other problems, in which efficient external memory algorithms can be obtained by simulation of well-known parallel algorithms. Other useful techniques for batched problems that we survey include distribution sweep (useful for spatial join in databases and all nearest neighbors), buffer trees (for priority queues, sorting, and batched R-tree construction in databases), and batched filtering and external fractional cascading (for GIS map overlay and red-blue line segment intersection).

Programming tools and environments are available for simplifying the task of programming for external memory. Experiments on some newly developed algorithms that incorporate the above paradigms, implemented using TPIE (Transparent Parallel I/O programming Environment), show significant speedups over popular methods.

Retour à la liste des séminaires Prisme

Algorithms for Range Searching in External Memory

Data sets in large geometric applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this talk, we discuss several recent developments in the design and analysis of online range searching algorithms in external memory, with special applications to spatial databases and geographic information systems (GIS).

In the online setting, data can be preprocessed and then updated and queried. Range searching is an important online problem in which the data consist of points in d-dimensional space, and queries are of the form "Report all points contained in the following hyperrectangle (or other sort of polygon)". For the I/O model, we discuss an optimal new interval tree data structure for a special case of two-dimensional range searching, and we investigate range queries in three dimensions. Several problems are still open. 

Retour à la liste des séminaires Prisme

Cabri-géomètre, en tant qu'implémentation du concept de géométrie dynamique, est essentiellement un micro-monde de géométrie. C'est à dire qu'il constitue un environnement offrant aà son utilisateur des primitives d'objets et de relations, qu'il a la possibilité d'étendre pour faciliter la résolution de tel ou tel problème exprimable dans un cadre graphico-géométrique. J'aborderai dans ma présentation certaines des questions relatives à la nécessité de préciser une axiomatique possible pour la géométrie dynamique, qui ne peut être réduite ni à la geometrie euclidienne (R^2), ni à l'une de ses implémentations, Cabri-géomètre. Bien sur comme ce n'est qu'avec l'outil informatique, que le concept même de géométrie dynamique a pu se développer, l'exposé abodera aussi certaines des difficultés informatiques rencontrées avec le développement de Cabri-géomètre.

PS: Cabri-géomètre est un projet IMAG pour la définition et la réalisation d'un environnement intelligent pour la géométrie. Le projet, démarré en 1985, a conduit à la réalisation du logiciel du même nom, disponible aussi sur la calculatrice TI-92 de chez Texas-Instruments, et diffusé aujourd'hui à plus d'un million d'exemplaires dans le monde.

Retour à la liste des séminaires Prisme

 Queries with Segments in Voronoi Diagrams

There are a number of proximity questions on sets of n points in the plane, such as Hausdorff distance between two point sets or nearest foreign neighbors for colored points, that can be answered in O(n log n) by computing Voronoi diagrams and querying with points. If we ask the same questions for line segments, we cannot use the same answer; although we can build the Voronoi diagrams for (disjoint) line segments, line segment queries may each intersect a linear number of cells.

In general, one would not expect segment queries to be efficient, since they could be used to solve "Hopcroft's problem" -- determine if any of $n$ given points lies on any of $n$ given lines -- and algorithms for Hopcroft's problem have a \Omega(n^{4/3}) lower bound in a natural model. We were surprised, therefore, that for n points and n disjoint segments, an algorithm can find the closest point to each segment in O(n log^3 n) time. This lets us compute Hausdorff distance and nearest foreign neighbors for disjoint segments in the same time.

This is joint work with Sergei Bespamyatnik.

Retour à la liste des séminaires Prisme

Les courbes optimales et sous-optimales dans le mouvement plan avec une borne sur la dérivée de la courbure

On consid\`ere le mouvement plan avec la vitesse uniforme et avec une borne sur la d\'eriv\'ee de la courbure, les conditions initiales et finales \'etant les coordonn\'ees, les angles tangents et les courbures au point initial et au point final.

L'int\'er\^{e}t de l'\'etude de ce probl\`eme provient de la planification des trajectoires d'un robot mobile de type voiture. Une trajectoire est dite optimale si elle est la plus courte possible. Dans la th\`ese on consid\`ere les deux cas -- avec ou sans points de rebroussement dans la trajectoire. Pour obtenir les conditions n\'ecessaires pour qu'une trajectoire soit optimale, on applique le Principe de Maximum de Pontryagine.

Dans le cas sans points de rebroussement on montre que si la distance entre le point initial et le point final (on la d\'esigne par $d$) est plus grande que $320\sqrt{\pi}$, alors, les courbes optimales sont, en g\'en\'eral, irr\'eguli\`eres, i.e. elles ont un nombre infini de points de commutation.

Dans les deux cas on montre comment construire des trajectoires sous-optimales, i.e. plus longues que les trajectoires optimales d'au plus une constante. Ces trajectoires consistent en 4 arcs de clotho\"{i}de et un segment de droite. On d\'emontre la sous-optimalit\'e des trajectoires construites. Dans le cas sans point de rebroussement on d\'efinit la construction pour la situation o\`u $d$ est plus grande que $3\sqrt{\pi }$; dans le cas avec points de rebroussement on d\'efinit la construction au cas o\`u $d$ est plus grande que $4\sqrt{2\pi }+|\kappa^0|/2+|\kappa^T|/2$ (ici on d\'esigne par $\kappa^0$, $\kappa^T$ les courbures initiale et finale).

Dans la th\`ese on commence aussi l'\'etude du probl\`eme o\`u l'acc\'el\'eration et la d\'eriv\'ee de la courbure sont born\'ees \`a la fois.

Retour à la liste des séminaires Prisme

Skip Lists Directionnelles et recherche de voisins sur Hyper-Cube. Applications au "drug design".

Etant donnee une base de donnees moleculaire M et une pathologie, une des methodes utilisees par les concepteurs de medicaments consiste a (1)tester au hasard un echantillon de molecules de M (2)selectionner les molecules les plus prometteuses de l'echantillon (3)tester de facon plus systematique les molecules ayant une structure similaire a ces dernieres. Un prealable a cette exploration fonctionnelle est donc le partitionnement de M en classes de molecules similaires et de taille homogene. Via le formalisme ad-hoc et en termes algorithmiques, le probleme revient alors a chercher des paires de points "voisins" sur un hyper-cube H_d={0,1}^d de grande dimension ---par exemple d=1500 pour M contenant n=10^4 molecules.

Les methodes classiques d'algorithmique geometrique ---diagrammes de Voronoi, box-trees, etc--- souffrant de constantes exponentielles en la dimension, nous presentons une solution a ce probleme fondee sur deux nouvelles structures de donnees probabilistes, les Skip Lists Directionnelles et les Skip Lists Directionnelles Recursives ---DSL et RDSL. En deux mots, une DSL est une sequence d'approximations imbriquees de l'hyper-cube H_d. Et une RDSL est une DSL recursive visant a partitionner l'ensemble de depart M de telle sorte que les points situes a une faible distance de Hamming soient affectes a la meme classe de la partition. D'un point de vue theorique, l'analyse des RDSLs est reliee aux hyper-graphes et systemes de Sperner, et donc difficile. En pratique, les temps de calcul resultant de ces constructions sont environ 50 fois plus rapides que ceux des algorithmes naifs.

Ce travail fait l'objet d'une collaboration avec Elf-Sanofi recherche.

Retour à la liste des séminaires Prisme

Résolution de dégénérescences par perturbation du problème ou de l'univers

Travail effectué en collaboration avec Pierre Alliez et Jack Snoeyink.
Nous décrivons deux approches permettant de supprimer les cas dégénérés dans certains problèmes géométriques. Nous appelons ces méthodes perturber le problème et perturber l'univers. Avec comme exemples privilégiés la triangulation de Delaunay en dimension 2 et 3 pour des métriques euclidiennes ou polygonales, nous montrons que ces approches permettent de concevoir simplement et efficacement une perturbation des points qui ne dépend pas d'une numérotation de ces points. Nous produisons de cette manière un résultat canonique, ce qui est important pour concevoir des jeux de tests ou des vérificateurs pour des algorithmes randomisés ou dynamiques.
Pour en savoir plus : http://www.inria.fr/RRRT/RR-3316.html

Retour à la liste des séminaires Prisme

Aide géométrique à l'aménagement de satellites

Nous nous intéressons dans cette thèse à des problèmes d'aménagement de satellites. Le but est de développer des algorithmes efficaces et robustes menant à des outils simples pour aider l'ingénieur du bureau d'études dans ses tâches répétitives d'aménagement.

Nous proposons un algorithme optimal qui calcule une section plane de la somme de Minkowski de deux polyèdres convexes et un algorithme efficace qui calcule l'union d'un ensemble de polygones par division et fusion. Nous avons soigneusement analysé la précision numérique nécessitée pour le fonctionnement correct de ces deux algorithmes et le traitement des dégénérescences géométriques qui peuvent apparaître.

Nous avons conçu le logiciel GEOTOOLS pour le placement d'une suite d'équipements et en particulier des antennes qui ont un champ de vision. GEOTOOLS permet le placement interactif d'un objet dans un aménagement partiel en visualisant les contraintes imposées par cet aménagement (l'espace admissible). La deuxième partie de cette thèse consiste en une expérimentation de GEOTOOLS sur des modèles réalistes de satellites en plaçant des séquences d'antennes interactivement et automatiquement.

Mots-clés : Géométrie algorithmique, placement de formes, espace libre, aménagement de satellite, robustesse, précision numérique

Retour à la liste des séminaires Prisme

A-forme et A-forme pondérée

 Nous présenterons un formalisme mathématique de la notion de forme d'un ensemble fini de points. Nous entendons par forme, une description de cet ensemble en termes de composantes connexes reflétant les formes perçues par un observateur humain. Nous définissons la forme d'un ensemble de points par une famille de graphes liés à la triangulation de Delaunay. Nous appelons cette famille A-forme où le paramètre A est un ensemble de points permettant à A-forme d'exhiber un certain niveau de détails. Dans cet exposé, nous présenterons les définitions, les propriétés et les algorithmes de A-forme et de sa version pondérée.

Retour à la liste des séminaires Prisme

 Skip Lists Directionnelles et recherche de voisins sur Hyper-Cube.
Applications au "drug design".

 Parmi les methodes recentes de conception de molecules pharmaceutiques, la synthese combinatoire consiste comme son nom l'indique a synthetiser de facon virtuelle des ensembles gigantesques de molecules a partir de grammaires. Mais tous les produits formes n'ayant pas le meme interet, a la synthese succede generalement une operation de regroupement des molecules par "similarite" et taille homogenes. En termes algorithmiques, le probleme revient alors a chercher des paires de points "voisins" sur un hyper-cube de grande dimension --par exemple $d=1500$ pour $n=10^4$ molecules.

Les methodes classiques d'algorithmique geometrique --diagrammes de Voronoi, box-trees, etc-- souffrant de constantes exponentielles en la dimension, nous presenterons une solution a ce probleme fondee sur des Skip Lists Directionnelles. Typiquement, les temps de calcul qui en resultent sont 50 fois plus rapides que ceux des algorithmes naifs ou lies aux reseaux de neurones de type Kohonen. Nous montrerons cependant que l'analyse de ces structures de donnees est reliee d'une certaine facon aux systemes de Sperner, et donc difficile.

Retour à la liste des séminaires Prisme

 Elimination based methods for solving the non-linear equations of mechanism and robot kinematics

 This talk will review the common methods of obtaining equations for the kinematic analysis and design of mechanical systems of linkwork. It will then point out the essential sine-cosine character of all these formalisms. Once this is established, the main body of the talk will deal with the solution of sets of sine-cosine equations. Emphasis will be placed on elimination methods, and especially on methods of obtaining auxiliary equations from the original set. This talk will review what we have learned in the last several years by use of elimination methods. It will be pointed out that classical techniques of elimination usual are too cumbersome, but with slight modifications the same basic concepts can lead to effective algorithms. A recent, as yet unpublished, use of such an approach will be used to illustrate both the method and some interesting properties of complex heretofore not analyzed systems.

Retour à la liste des séminaires Prisme

 Structures combinatoires en modélisation géométrique :
mécanismes de définition et complexité

 L'utilisation de structures combinatoires pour representer la topologie de subdivisions d'espaces geometriques se developpe dans de nombreux modeleurs commerciaux. Plusieurs problemes se posent : la validite topologique de la structure, la gestion des informations de plongement, necessaires pour l'obtention de la description d'un objet geometrique, la mise en oeuvre d'operations de construction et de calcul de proprietes geometriques, la complexite en espace des structures et la complexite en temps des operations.

La premiere partie de l'expose a pour objectif la presentation de structures combinatoires et des mecanismes utilises pour deduire leur definition de celle des ensembles simpliciaux (structure bien connue en topologie algebrique, permettant la manipulation de triangulations quelconques) : nous montrons comment deduire la definition d'autres structures "simpliciales" decrivant des subdivisions dans lesquelles les cellules sont des produits cartesiens de simplexes (ensembles simpliciaux cubiques, ensembles simploidaux), ainsi que les relations naturelles permettant d'utiliser ces structures pour la manipulation d'espaces de forme libre. Il est aussi possible de fonder sur ces notions la definition de structures cellulaires (ie decrivant la topologie de subdivisions dans lesquelles les cellules sont "quelconques"). Certains mecanismes de reduction de la complexite en espace de ces structures sont aussi evoques, ainsi que les consequences pour les definitions et complexites de certaines operations classiques.

La deuxieme partie de l'expose porte plus particulierement sur l'evaluation de la complexite de ces representations. Dans un premier temps, une etude statistique du nombre moyen de cellules est menee, permettant d'etablir certains rapports entre nombres (de cellules incidentes/adjacentes a d'autres cellules, genre, etc). Cette etude est menee pour le cas 2D, et certains resultats sont etendus en dimension 3 et plus generalement en dimension n. Ces resultats sont ensuite appliques a l'evaluation de la complexite en espace de structures topologiques et la complexite en temps des operations d'acces aux elements de ces structures (cad les operations de base de manipulation des structures, qui conditionnent la complexite des operations plus elaborees).

Retour à la liste des séminaires Prisme

Description des incertitudes geometriques de l'information geographique

L'evaluation de la qualite des donnees geographiques se fait habituellement par l'estimation de cinq composantes : qualite geometrique, qualite semantique, genealogie, coherence logique, actualite. Un rapide survol de ces notions est propose, avant d'exposer les resultats d'une recherche plus poussee sur la composante geometrique, en particulier sur les objets lineaires et surfaciques.

Les incertitudes geometriques des donnees geographiques peuvent etre considerees comme des variables aleatoires, ce qui permet la mise en place d'une modelisation statistique. Trois approches ont ete testees sur des objets lineaires : modelisation par loi de repartition, modelisation par variogrammes, et modelisation par fractales statistiques. L'instanciation de ces modeles necessite l'usage de diagrammes de Voronoi generalises. Ce point est presente en detail, et d'autres exemples d'utilisation des diagrammes de Voronoi sont fournis a cette occasion. Des relations entre les modeles obtenus sont avancees, ainsi que des methodes de propagation ou de simulation des incertitudes dans les systemes d'informations geographiques.

Le cas des objets surfaciques est aborde avec d'autres methodes. Les ecarts surfaciques des objets geographiques comprennent des ecarts de forme et des ecarts de position. Plusieurs methodes sont presentees : certaines sont issues des techniques d'analyse de formes, d'autres sont issues de distances mathematiques. Elles ont ete etablies apres la mise au point d'un algorithme d'appariement d'objets surfaciques, teste sur des maisons et des zones d'occupation des sols.

Retour à la liste des séminaires Prisme

 Recent Progress on The Greedy Flip Algorithm

I will present a new method to implement the flip operation of the Greedy Flip Algorithm, an optimal time and linear working space output sensitive algorithm to compute the tangent visibility graph of a collection of pairwise disjoint bounded convex sets of constant complexity.

The method should be easy to implement since it uses only primitive data structures, that is arrays and/or linked structures (collections of nodes interconnected by pointers) to represent maps, sets, and lists. (The previous method uses splittable queues.)

The method was partially suggested by a careful theoretical and practical comparison of the Greedy Flip Algorithm and the so-called Topological Sweep Method of Edelsbrunner and Guibas. I will report on this comparison during the talk, in particular I will show that the upper and lower horizon trees, properly interpreted, are disjoint spanning trees of good greedy pseudo-triangulations whose union is a (pseudo)-quadrangulation, and I will relate in a precise sense the update operations of the horizon trees to the flip operation of the Greedy Flip Algorithm.

(Joint work with P. Angelier.)

Retour à la liste des séminaires Prisme

 Dey's improvement on the k-set bound, genealogy and related results

Le but de l'expose est de faire une synthese des resultats qui ont conduit a la nouvelle borne de O(n k^{1/3}) par Tamal Dey sur le nombre de k-sets. On partira de l'article original de Lovasz (1971) et de Erdos, Lovasz, Simmons et Straus (1973) qui prouvent une borne de O(n sqrt(k)), mentionnera sans s'attarder la borne de Pach, Steiger et Szemeredi (1992) de O(n sqrt(k)/log*(k+1)) et les bornes recentes de Agarwal, Aronov, Chan, et Sharir (1997) qui generalisent a O(n k^{5/3}) les bornes du probleme analogue tri-dimensionnel. On concluera sur l'extension recente de Andrzejak, Aronv, Har-Peled, Seidel et Welzl.
Comme la borne de Dey est tres simple, j'essaierai de donner a chaque fois une courte preuve des resultats, meme si elle differe de celle donne dans les articles originaux.

Retour à la liste des séminaires Prisme

 Degenerate convex hulls on-line in any dimension

The main goal of this talk is to show how a simple modification of the formulation of an algorithm by Clarkson and Shor can handle the case of degenerate sets of points for computing convex hulls on-line in $\R^d$, $d\geq 2$. Degenracies in this context have been studied and many solutions have been proposed in the past. When the points are inserted on-line, only an algorithm by Burnikel, Mehlhorn, and Schirra is appropriate, but its analysis remains difficult and unsolved in the degenerate case (even if the algorithm is simple and has been implemented and shown to behave nicely). For our algorithm, a *simple* analysis allows to maintain the expected time complexity within $O(n^{\floor{d/2}})$. The analysis uses connections between regions (from Clarkson and Shor), pivots, flags (from homology theory), and barycentric triangulations.

Retour à la liste des séminaires Prisme

 Cross ratios and angles determine a polygon

We prove that a unique simple polygon is determined, up to similarity, by the interior angles at its vertices and the cross-ratios of diagonals of any given triangulation. (For a diagonal edge e, shared by two triangles whose other edges have length a, b and c, d, the cross-ratio is ac/bd.) This establishes a conjecture of Driscoll and Vavasis, and shows the correctness of a key step of their algorithm for computing a conformal mapping of a disk to a polygon.

I will describe how this conjecture arises from their interesting^A work on mesh generation for numerical methods, how the solution relates to interesting^B families of curves, and some interesting^C open problems that remain. I hope the talk will be interesting^D.

----
Definitions of "interesting":
A. novel combination of continuous and discrete mathematics.
B. familiar curves in surprising places.
C. difficult.
D. stimulating enough to avoid audience ennui.

Retour à la liste des séminaires Prisme

 Robustesse et Géométrie

Différentes approches pour résoudre les problèmes de robustesse des algorithmes géométriques seront evoquées. Les points suivants seront abordés de façon plus ou moins détaillée :

LES APPROCHES ISSUES DE LA GEOMETRIE ALGORITHMIQUE
- l'approche "arithmétique exacte" :
questions ouvertes, intérêts et limites de l'approche exacte
*croissance de la longueur des coefficients, et des degrés
*nécessité et difficulté de l'arrondi géométrique
- l'approche "coh'erente"
- ...
III LES AUTRES APPROCHES, explorées par les autres domaines de l'informatique géométrique (CAO, synthèse d'images: rendu, animation). Un probleme typique est l'évaluation du CSG, et non l'enveloppe convexe. Liste de quelques approches discutées :
1-approche discrete
2-approximation lineaire par morceaux
3-approche "tout CSG", avec lancer de rayons et Marching Cube, etc
En gros, cette approche rejette les representations par frontieres. On se sert de CSG et de lancer de rayons (qui est approximatif mais robuste). Quand on veut une evaluation des frontieres, on utilise une methode fruste mais robuste, telle que le Marching Cube. Une difficult'e est la prise en compte des surfaces parametrees qui s'insere assez mal dans le contexte CSG. Se pose aussi (mais il se poserait de toute facon) le probleme du nommage permanent (persistant naming).
4-approche par partition spatiale et analyse d'intervalles
L'approche precedente procede par echantillonnage. Celle-ci corrige les possibles d'efauts de sous-'echantillonnage. Un des traits de cette approche est que le resultat peur contenir des zones "on ne sait pas".
5-g'eom'etrie floue (Segal Sequin Patrikalakis) ou "tolerant modelling"
on utilise des BReps classiques, mais chaque entite est entouree d'un halo d'incertitude. Cette approche reste assez empirique (pas de preuve...). Un debut de formalisation est :
6-approche "continuiste" (analyse constructible, Lieutier)
On rejette le modele classique d'ordinateur et de calcul. A la place, on utilise le modele o`u l'ordinateur ne peut pas repondre aux tests d'egalit'e. Par contre, il peut calculer avec une precision aussi grande qu'on veut (mais finie). Avec une telle machine, on montre que seules sont calculables les fonctions continues.

Retour à la liste des séminaires Prisme

 Dynamic Data Structures for Fat Objects and Their Applications

joint work with
# Alon Efrat: School of Mathematical Sciences, Tel Aviv University, Tel-Aviv 69982, Israel.
# Matthew J. Katz: Departments of Industrial Engineering & Management and Mathematics & Computer Science, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel.
# Micha Sharir: School of Mathematical Sciences, Tel Aviv University, and Courant Institute of Mathematical Sciences, New York University.

We present several efficient dynamic data structures for point-enclosure queries involving convex fat objects in R2 or R3. These structures are more efficient than alternative known structures because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to three problems:
(i) Finding a perfect matching between a set of points and a set of convex fat objects.
(ii) Finding a piercing set for a collection of convex fat objects, whose size is within a constant factor off the optimum size.
(iii) Construct a data structure for answering segment-shooting queries: Given a set of objects in the plane as above, and a query oriented segment r, find the first object hit by r.

Retour à la liste des séminaires Prisme

 Virtual Endoscopy on Siemens Post Processing Workstation

 Le produit d'endoscopie virtuelle "Flythrough" vient d'être mis au point chez Siemens Corporate Research. C'est un système de visualisation 3D pour l'imagerie médicale.

Plusieurs modules de ce système sont basés sur des travaux effectués à l'INRIA dans le projet Prisme : la reconstruction tri-dimensionnelle à partir de coupes parallèles, la détection de collisions, et la planification de trajectoires.

Le rendu volumique est en cours d'intégration. Quelques résultats et problèmes liés au placage de textures et au lissage seront également présentés.

Mots-clefs: modèle polyédrique, placage de texture, rendu volumique.

Retour à la liste des séminaires Prisme

 - On Point Covers of c-Oriented Polytopes
- Combinatorial optimization algorithms for radio network planning

On Point Covers of c-Oriented Polytopes
Let S be any family of n c-oriented polytopes of the d-dimensional Euclidean space Ed, i.e., bounded intersection of halfspaces whose unit normal vectors of facets belong to a fixed collection of c distinct unit vectors. Denote by $\phi(\S)$ and $\tau(\S)$ respectively the maximal number of pairwise disjoint polytopes of S (packing or independence number) and the minimum number of points so that each object contains at least one of these points (0-transversal} or covering number). Let $\Gn(2,c)$ be the Gallai number of pairwise intersecting $c$-oriented polytopes (e.g., $\Gn(2,c)=O_d(1)$ for homothets with $c\geq d+1$). In this paper, we prove the following:
$$\tau(\S )\leq\Gn(2,c)\phi(\S )\log _2 ^{c-1}(\phi(\S )+1).$$

Moreover, we give an $O\left(t(n,c)+nc\log\phi(\S )\right)$-time algorithm with linear storage that computes a $0$-transversal of size at most $\Gn(2,c)\phi(\S )\log _2 ^{c-1}(\phi(\S )+1)$, where $t(n,c)$ is the time required to pierce pairwise intersecting $c$-oriented polytopes. Our bound becomes $\tau(\S)=O_d(\Gn(2,c)\phi(\S))$ if objects are more or less of the same size. In the case of $\alpha$-fat $c$-oriented polytopes, translates or homothets, we show that $\Gn(2,c)=O(\alpha)^d$, $\Gn(2,c)\leq d^{d}$ and $\Gn(2,c)\leq (3d^{\frac{3}{2}})^d$ respectively. In the latter cases, we give algorithms in $t(n,c)=\Theta _d (nc)$ time.

This paper is also devoted to give a (partial) state of the art of the geometric set cover problem.

Applet available at http://www-sop.inria.fr/prisme/personnel/nielsen/JPIERCE/pierce.html
 

Combinatorial optimization algorithms for radio network planning
joint work with:
# Patrice Calégari
# Frédéric Guidec
# Pierre Kuonen
Swiss Federal Institute of Technology, 1015 Lausanne, Switzerland

One of the key issues telecommunication companies must face when deploying a mobile phone network is the selection of a good set of sites among those possible for siting fixed transmitters. The problem comes down to serving a maximum surface of a geographical area with a minimum number of such transmitters.

A geographical location is said to be served when it can receive the signal broadcast by a transmitter with a given quality of service. In our implementation, geographical locations are discretised on a regular grid, and the area served by each transmitter is computed by a radio wave propagation prediction tool. A set of geographical locations that are potentially served by a same set of transmitters is called a cell. Let us consider the set $C$ of all potentially served cells, and the set $T$ of all potential transmitter locations. Let $G$ be the graph $(C\cup T,E)$, where $E$ is a set of edges such that each transmitter location is linked to the cells it serves.

The problem we consider recalls the {\em Set Covering Problem} ({\sc SCP}). It however differs slightly from the {\sc SCP} in that the goal is to select a satisfactory subset of transmitters that ensures a ``good'' service in the area, and not to guarantee that the whole area is served. The latter point means that non-combinatorial parameters are to be considered, such as a target service ratio, etc.

We have developped four different algorithms to solve this radio network planning problem. (The resulting {\sl C++} package currently weighs about $10000$ code lines.) During the talk we will present comparative benchmarks obtained experimentally when siting transmitters in the French region ``les Vosges'' (hilly region) and a district of the city of Geneva using the following algorithms:
* Greedy-like algorithms.
* Island-based generational replacement Genetic Algorithms.
* Darwinism algorithms using $\epsilon$-nets (fixed Vapnik-Chervonenkis dimension).
* `Fat' greedy-like algorithms.

Retour à la liste des séminaires Prisme

 How to Move a Mountain: Geographic Information Systems (GIS) Terrain Models on WWW

 Many of the computational geometers' favorite data structures are planar graphs that are canonically determined by a set of geometric objects and take \Theta(n \log n) time to compute. Using the Delaunay triangulation as an example, we show that, given such a structure, one can determine a permutation of the data in O(n) time such that the diagram can be recomputed from the permuted data in O(n) time by a simple incremental algorithm.

 In a Geographic Information Systems (GIS), this allows us to store terrain models based on the Delaunay triangulation in flat files without disrupting other applications, and to read or transmit these models progressively---producing a sequence of better and better approximations as a model is read or received. This is demonstrated by a Java applet that we are developing.

 The theorems are work with Marc van Kreveld from Utrecht, and the Java applet is work with Bernd Juenger, who is visiting UBC from Darmstadt.

Retour à la liste des séminaires Prisme

 Recherche de voisin en grande dimension et clustering sur hyper-cube

 ABSTRACT: Etant donnes n points d'un espace d-dimensionel Euclidien, le probleme du plus proche voisin se formule comme suit: quel pre-traitement appliquer a ces points pour trouver le plus vite possible le plus proche voisin ---selon une metrique euclidienne--- d'un point quelconque?

Nous presenterons d'abord 2 algorithmes recents de J. Kleinberg (ACM STOC'97), qui sont les premiers a founir une approximation au probleme precedent avec un temps de requete non exponentiel en d.

Nous evoquerons ensuite une application potentielle de ces algorithmes a un probleme de clustering sur un hyper-cube issu de la chimie ---l'hyper-cube de dimension d etant simplement l'espace dans lequel une molecule consideree comme une sequence de d fragments moleculaires est representee par un point.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

On Computing an ordinary line.

 ABSTRACT: Given a finite set of points in the plane, not all collinear, there exists a line going through exactly two points. Such a line is called an ordinary or Sylvester (in memmory of J. Sylvester who first proposed the problem). In this talk we address the algorithmic problem of finding such a line.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Huffman Codes for Morse Codes and Related Problems.

 ABSTRACT: Suppose we are given a message composed of n words that occur with given frequencies p_1, p_2, . . ., p_n. The Huffman encoding problem is to encode the message using a prefix-free code over the coding alphabet {0, 1} in a way that uses the least space. It is well known that this problem can be solved in O(n log n) time.

Now suppose that the encoding alphabet {0, 1} has been replaced by {., -}, as in Morse Code, or any other alphabet in which the letters do not have the same length. Suppose too that length(.)=1 and length(-) = c. It is unknown whether the problem of finding a minimum cost encoding for such unequal cost alphabets is NP-hard, polynomial time solvable, or something else.

The previously best known algorithm for solving this problem was given by Karp who reduced it to integer linear programming. In this talk we present a new simple O(n^{c+2}) algorithm. While still not resolving the P vs. NP-hard status of the problem this seems to be the first algorithm that works in polynomial time for fixed letter costs.

This is joint work with Gunter Rote.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

 Evaluation des maillages de surfaces, application à la simplification de maillages

 RESUME: On presente quelques critères destinés à l'évaluation des triangulations de surfaces (dans le contexte des méthodes aux éléments finis). Ces critères sont basés sur l'analyse de propriétés géométriques des triangulations. Une application de ces critères pour gouverner un algorithme de simplification (décimation) de maillages est presentée.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

 Report: Workshop on Bounded Radius Curvature

 RESUME: Je vous parlerai du workshop on bounded radius of curvature problems qui s'est deroule au Bellair Research Institute of McGill du 9 au 16 mars 1997. Etaient present Pankaj Agarwal (Duke University), Therese Biedl (Rutgers University), Hazel Everett (UQAM, Montreal) Micha Gadau (Freie Universitat, Berlin), moi meme, Steve Robbins (McGill), Subbash Suri (Washington University, St. Louis), Sue Whitesides (McGill), Steve Wismath (on sabbatical at McGill from U. Lethbridge, Alberta, Canada).

Je vous presenterai les resultats obtenus sur le probleme du calcul de plus courts chemins de courbure bornee dans un polygone convexe. Je decrirai egalement les autres problemes que nous avons abordes.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Modélisation géometrique de structures anatomiques extraites d'un volume numérique

 RESUME: Les techniques d'imagerie médicale tridimensionnelle nous permettent de visualiser les organes et régions anatomiques du corps humain. Ces images fournissent au clinicien une description précise des structures anatomiques en meme temps qu'une évaluation qualitative de leurs paramètres géométriques. Cependant, l'obtention de paramètres caractéristiques pour le diagnostic ou la préparation de l'acte chirurgical nécessite une véritable modélisation géométrique de ces structures.

Une méthodologie originale s'appuyant sur la dualité surface/volume sera présentée. Cette approche, essentiellement interactive, permet une analyse fine du volume numérique à travers un modèle structure. Une segmentation grossière du volume numérique est effectuée par l'intermédiaire d'un processus interactif d'analyse de texture ; une analyse des formes obtenues et leur caractérisation par des surfaces de forme libre permettent de structurer les formes recherchées et d'initialiser un processus de modèle deformable à l'interieur du volume numérique.

Certains aspects géométriques (raccordement de surfaces) ou liés à la communication homme/machine (interaction avec l'espace de représentation des propriétés texturelles) seront decrits plus en detail.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Indexations d'images

RESUME: Comment peut on indexer des images par le contenu? Quelle type d'interrogations une telle indexation pourra-t-elle permettre? Quels problèmes scientifiques cela pose-t-il?

J'essaierai de répondre à ces questions, au moins partiellement. Une partie de l'exposé présentera les outils qu'a développés Cordelia Schmid dans notre projet et les problèmes techniques qu'il a fallu re'soudre pour aboutir à une complexité raisonable pour les accès dans la base que nous avons consitutée. Dans une seconde partie, je m'attacherai à poser le probleme des besoins d'accès dans des bases d'images d'une facon plus generale, et a positionner ces besoins par rapport aux réponses actuellement disponibles à travers quelques maquettes accessible à travers le monde.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Algorithmes efficaces pour l'étude des zéro réels des systèmes zéro-dimensionnels

RESUME: L'objet de cet exposé est de présenter des outils mathématiques et logiciels pour l'étude des zéro réels des systèmes zéro-dimensionnels par le calcul exact.

Si I est un sous-ensemble de K[X_1,...,X_n] (K est un corps) est l'idéal engendré par les polynômes définissant le système étudié, le prérequis de la famille de méthodes que nous presentons est la connaissance de l'algèbre quotient K[X_1,...,X_n]/I - définie complêtement, par exemple, par la donnée d'une base de Gröbner, calculée pour une ordre admissible quelconque.

Dès lors que I est zéro-dimensionnel (admet un nombre fini de zéros dans C^n, C étant la clôture algébrique de K) - condition pouvant être vérifiée algorithmiquement - nous proposons une méthode (Représentation Univariée Rationnelle) pour éliminer n-1 variables et permettant donc de se ramener à l'étude de polynômes de K[T], sans perte d'information sur les racines (nombre, multiplicités, caractère réel). Dans le cas de systèmes à coefficients rationnels nous montrerons comment, en particulier, isoler les coordonnées des racines réelles par des intervalles à bornes rationnelles.

Toujours dans le cas o\`u I est zéro-dimensionnel, et si K est un corps ordonné, nous presenterons ègalement des outils (algorithme de Hermite) permettant de compter directement le nombre de zéros de I dans R^n (R est la clôture réelle de K) vérifiant (ou non) un nombre arbitraire d'inégalités polynomiales.

Une solution pratique sera décrite pour chacun des points abordés.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Suivi et mise en correspondance de structures deformables

 RESUME: La modelisation spatio-temporelle de phenomenes naturels observes via teledetection implique souvent la gestion de mouvements hautement non rigides: le suivi de nuages en meteorologie, le suivi de structures oceaniques (fronts, tourbillons) ou, dans le cadre de la surveillance de la pollution, le suivi de nappes de petrole en sont trois exemples classiques. Les problemes specifiques proviennent du fait que les structures etudiees ne sont pas necessairement des objets a proprement parler, mais plutot des fluides en mouvement. Aussi observe-t-on frequement de grandes deformations, pouvant affecter jusqu'a la topologie de la structure: par exemple, les nuages accompagnant une tempete tropicale peuvent se regrouper en une grande structure nuageuse qui plus tard se desagrege. Par ailleurs, selon le type d'imagerie, la resolution temporelle du capteur peut etre relativement importante: les images oceanographiques sont typiquement acquises a une frequence d'un ou deux jours. Dans ce cas, on ne peut esperer la continuite temporelle du mouvement, les observations successives de la structure peuvent differer sensiblement.

Les points durs de telles modelisations concernent principalement la mise en correspondance de deux observations successives de la structure, le calcul des trajectoires ponctuelles et la reconstitution du mouvement intermediaire. En particulier dans le cas ou les deux occurrences sont tres differentes, ces problemes doivent idealement etre traites en ajoutant des connaissances sur le mouvement, de type equations de mecanique des fluides. Ces connaissances sont malheureusement indisponibles ou partielles. Aussi modelise-t-on l'evolution par d'autres types de contraintes. Le projet AIR a ainsi developpe parallelement trois methodes differentes, qui sont l'objet de la presentation:

• le calcul d'une surface interpolante, regie par des contraintes geometriques, repond "sur le papier" aux trois problemes mais s'avere complexe a mettre en oeuvre et relativement inadapte aux changements de topologie;
• les formulations implicites sont plus adaptees au changement de topologie, le probleme est alors la signification physique des contraintes. Deux formulations implicites ont ete developpees:
• par "soft object": la structure est modelisee par des points de controle ayant un certain rayon d'influence, le mouvement est modelise par des contraintes sur celui des points de controles.
• par "level set": les trajectoires sont les geodesiques d'une surface definissant un cout, fonction de la distance a parcourir.

Automatic Reconstruction of 3D CAD Models from Digital Scans

We present an approach for the reconstruction and approximation of 3D CAD models from an unorganized collection of points. Applications include rapid reverse engineering of existing objects for use in a synthetic computer environment, including computer aided design and manufacturing. Our reconstruction approach is flexible enough to permit interpolation of both smooth surfaces and sharp features, while placing few restrictions on the geometry or topology of the object.

Our algorithm is based on alpha-shapes to compute an initial triangle mesh approximating the object's surface. A mesh reduction technique is applied to the dense triangle mesh to build a simplified approximation, while retaining important topological and geometric characteristics of the model. The reduced mesh is interpolated with piecewise algebraic surface patches which approximate the original points.

The process is fully automatic, and the reconstruction is guaranteed to be homeomorphic and error bounded with respect to the original model when certain sampling requirements are satisfied. The resulting model is suitable for typical CAD modeling and analysis applications.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Robustness in Computational Geometry

ABSTRACT: In the context of methodologies intended to confer robustness to geometric algorithms, we elaborate on the exact computation paradigm and formalize the notion of degree of a geometric algorithm, as a worst-case quantification of the precision (number of bits) to which arithmetic calculation have to be executed in order to guarantee topological correctness. A formalism is also proposed for the expeditious evaluation of algorithmic degree. As an application of this paradigm and an illustration of our general approach, we consider the important classical problem of proximity queries in 2 and 3 dimensions, and develop a new technique for the efficient and robust execution of such queries based on an implicit representation of Voronoi diagrams. This new technique gives both low degree and fast query time, and for 2D queries is optimal with respect to both cost measures of the paradigm, asymptotic number of operations and arithmetic degree.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Geometric Perspectives in the Mechanics and Control of Robotic Locomotion

ABSTRACT: A significant body of research has been developed in the area of robotic locomotion. However, prior studies have been focused either on a particular set of assumptions or a particular robot morphology. To date there exists no unifying methodology for analyzing or controlling robotic (or biological) locomotion. Ultimately, we seek a "mechanics theory" and a "control theory" for robotic locomotion which is both rigorous and uniformly applicable to a broad class of locomotory problems. This talk summarizessome recent work on the development of unifying principles for a broad class of "undulatory locomotion" problems:
Undulatory locomotion is the process of generating net displacements of a robotic mechanism via a coupling of internal deformations to an interaction between the robot and its environment. Actuatable wheels, tracks, or legs are not necessary.
Common biological counterparts of undulatory locomotion include worms, snakes, amoeba, and fish. we limit these interactions to those modeled by nonholonomic kinematic constraints. This restriction allows us to model a rich class of systems and results in enough structure to make the problem tractable.

First, we make the connection between locomotion and some recent advances in geometric mechanics. For example, all locomotion problems (not just undulatory ones) can be cast in the framework of principal fiber bundles. Second, using this geometric insight, we derive a specialized form of the dynamical equations for mechanical systems with Lagrangian symmetries and nonholonomic constraints (which are characteristic of undulatory locomotors). Third, we show how these results lead to a simple and appealing insight into undulatory locomotion. Fourth, we show how these equations lead naturally to nonlinear controllability analysis of undulatory systems. The talk will include video demonstrations of a novel "snakeboard" robot and other experiments which illustrate the theory. Finally, we show that the framework presented here is in fact a superset of prior work on the mechanics of wheeled nonholonomic vehicles and free-floating satellites.

Time permitting, preliminary work that extends this geometric framework to legged locomotion will be discussed. The extension is based on the development of control theory on stratified sets.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

The Mechanics of Grasping and Fixturing

ABSTRACT: A configuration space approach is used to analyze the mobility of multiple rigid objects in point contact. These objects may be the fingers of a multi-fingered robotic gripper, the fixtures of an industrial assembly, or the legs of a multi-legged system undergoing quasi-static locomotion. We show that mobility is a local phenonmena, and not an infinitesimal one. Hence, our mobility analysis includes not only the points of contact but also includes the curvature of the contacting bodies in the analysis of mobility. Prior researchers have believed that the classical force closure condition is a necessary and sufficient condition to immobilize an object. We show that it is in fact sufficient, but not necessary. To generalize the force closure concept, new concepts of first and second order closure are introduced. The extension of this theory to include gravity and compliance is briefly reviewed, and an example showing how to compute all the immobilizing grasps of a planar object is given.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Removing Degeneracies in Computational Geometry

Existing methods for removing degeneracies in computational geometry can be classified as either approximation or perturbation methods. These methods give the implementer two rather unsatisfactory choices: find an approximate solution to the original problem given, or find an exact solution to an approximation of the original problem. We address an alternative approach that has received little attention in the computational geometry literature. Often a typical computational geometry paper will make a non-degeneracy assumption that can in fact be removed (without perturbing the input) by a global rigid transformation of the input. Once the solution is obtained on the transformed non-degenerate input, the solution can be transformed back trivially to yield the solution to the original problem. In these situations, by applying suitable pre- and post-processing steps, we obtain the exact solution to the original problem using an algorithm that assumes a non-degenerate input, even when that input is in fact degenerate.

We consider several non-degeneracy assumptions that are typically made in the literature, propose algorithms for performing the pre- and post- processing steps that remove these degeneracies, analyse their complexity, and for some of these problems we give lower bounds on their worst-case complexity.
The assumptions considered here include:
(1) no two points in the plane have the same x-coordinate,
(2) no two points in space lie on a vertical line,
(3) no two points in space have the same x-coordinate,
(4) no three points in space lie on a vertical plane,
and (5) no two line segments lie on a vertical plane.

We propose low-degree polynomial-time solutions for the decision, computation and optimization versions of all these problems.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Sensor Based Motion Planning: the Hierarchical Generalized Voronoi Graph

ABSTRACT: ``Sensor Based Planning'' incorporates sensor information, reflecting the current state of the environment, into a robot's planning process, as opposed to classical planning, which assumes full knowledge of the world's geometry prior to planning. Sensor based planning is important for realistic deployment of autonomous robots because: (1) the robot often has no a priori knowledge of the world; (2) the robot may have only a coarse knowledge of the world because of limited memory; (3) and the world model is bound to contain inaccuracies which can be overcome with sensor based planning strategies.

This talk will focus on one problem in sensor based motion planning: how to build a roadmap for a bounded environment when there is no apriori knowledge of this environment,, but there do exist sensors which can measure distance information. We introduce the Hierarchical Generalized Voronoi Graph (HGVG) as a basis for a roadmap. We then give a scheme to incrementally construct the HGVG using only local line-of-sight range data. The theory is demonstrated in experiments.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

PATTERN MATCHING IMAGE COMPRESSION:
Theory, Algorithms and Experiments

We describe a non-transform image compression technique based on approximate pattern matching, that we propose to call Pattern Matching Image Compression (PMIC). The main idea behind it is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately (e.g., D% of mismatches are allowed) occurs in the already processed image. We give new, efficient algorithms for performing computations motivated by this scheme, and describe the compression ratios experimentally obtained. This scheme turns out to be competitive with JPEG and wavelet compression for graphical and photographical images. A unique feature of the proposed algorithm is that an asymptotic performance of the scheme can be theoretically established. More precisely, under stationary mixing probabilistic model of an image and fixed maximum distortion level D, we show that the compression ratio is asymptotically equal to the so called generalized Re'nyi entropy. This entropy is in general smaller than the optimal rate distortion function, but there is numerical evidence that these two quantities do not differ too much for small and medium values of D. In this talk, we discuss theoretical, algorithmic and experimental results of this new compression scheme.

Joint work with M. Atallah, Y. Genin and T. Luczak

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Les courbes optimales et sous-optimales dans le mouvement plan avec une borne sur la dérivée de la courbure.

RESUME: On consid\`ere le mouvement plan avec vitesse uniforme et avec une borne $B$ sur la d\'eriv\'ee de la courbure, les conditions initiales et finales \'etant les coordonn\'ees, les angles tangents et les courbures au point initial et au point final.

L'int\'er\^{e}t de l'\'etude de ce probl\`eme provient de la planification des trajectoires d'un robot mobile de type voiture. Une trajectoire est dite optimale si elle est la plus courte possible. Dans la th\`ese on montre comment construire des trajectoires sous-optimales, i.e. plus longues que les trajectoires optimales d'au plus une constante ne d\'ependant que de $B$. Ces trajectoires consistent en 4 arcs de clotho\"{i}de et un segment de droite. On d\'emontre la sous-optimalit\'e des trajectoires construites. On consid\`ere les deux cas -- avec ou sans point de rebroussement dans la trajectoire. Dans le cas sans point de rebroussement on d\'efinit la construction pour la situation o\`u la distance entre le point initial et le point final (on la d\'esigne par $d$) est plus grande que $3\sqrt{2\pi }/{\sqrt{B}}$; dans le cas avec points de rebroussement on d\'efinit la construction o\`u $d$ est plus grande que $8\sqrt{\pi }/{\sqrt{B}}+|u^0|/B+|u^T|/B$ (ici on d\'esigne par $u^0$, $u^T$ les courbures initiale et finale). Dans le cas sans points de rebroussement on montre que si $d$ est plus grande qu'une constante ne d\'ependant que de $B$, alors les courbes optimales sont, en g\'en\'eral, irr\'eguli\`eres, i.e. contiennent une infinit\'e de points de discontinuit\'e des fonctions de contr\^{o}le.

Dans la th\`ese on commence aussi l'\'etude du probl\`eme o\`u l'acc\'el\'eration et la d\'eriv\'ee de la courbure sont born\'ees \`a la fois.

La m\'ethode principale utilis\'ee dans la th\'ese est le Principe de Maximum de Pontryagine.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

Modelisation interactive

RESUME: La recherche de techniques de modélisation et d'animation 3D interactives et générales constitue l'objectif des travaux présentés. En effet, les phases de modélisation et de contrôle de l'animation sont souvent laborieuses pour l'utilisateur, faute d'outils bien adaptés à ses besoins. La puissance d'un système de modélisation et d'animation provient de la diversité des outils offerts à l'utilisateur. L'exposé présentera les résultats de plusieurs études développées dans ce cadre.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

RESUME: L'action Genome de l'INRIA-Rocquencourt developpe un logiciel de comparaisons de sequences nucleiques et proteiques, denomme LASSAP . LASSAP est concu pour traiter les problemes de recherche de similarites et d'alignements a grande echelle. Il repond aux besoins: - des projets scientifiques en biologie moleculaire qui requierent du calcul intensif, - des centres de sequencage a haut debit, - des centres de services de'sirant offrir des temps de reponse de qualite, - des centres de bioinformatique en charge de la construction et de la maintenance des grandes banques de donnees.

Apres avoir presente les differents niveaux d'analyses cartographiques d'un genome, nous detaillerons la problematique de recherche de similarite's entres sequences primaires, et donnerons les quelques grandes tendances algorithmiques ainsi que les axes de recherche dans le domaine. Nous aborderons ensuite les limitations courantes des programmes actuels dans le contexte d'un flux de donnees toujours croissant, et exposerons en quoi LASSAP offre une approche novatrice dans le domaine.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme

 Recent Results on the Reconfiguration of Chains

 A {\em chain} consists of a sequence of $n$ rigid rods connected together at their endpoints, about which the rods may rotate freely. Despite their simplicity, such linkages are known to present some (seemingly) intractable motion planning problems, even in the plane. On the other hand, many problems for chains can be solved efficiently in spite of having a number of degrees of freedom that varies with the problem instance.

Here, by contrast, we study chains and their environments in a coordinated way, asking what properties of the combination guarantee that certain problems can be solved easily. Thus we aim to move beyond considering a particular chain in a particular enviroment in a case by case fashion. Given an environment, can we compute chain properties, based on that environment, that when satisfied guarantee fast solutions to reconfiguration or reachability problems? We show some interesting ``yes'' answers.

Joint work with Naixun PEI.

Retour a la liste des seminaires Prisme
Retour a la page d'accueil Prisme