Séminaire Algo

2007

I will talk about $\lambda$-Policy Iteration algorithm, a parameterized algorithm for solving optimal control problems, initially proposed by Bertsekas and Ioffe. It generalizes several standard algorithms: when $\lambda=0$ it is equivalent to Value Iteration and when $\lambda=1$ to Policy Iteration. Also, it has connections with Temporal Difference Algorithms, which where introduced in the Reinforcement Learning community.

I will present an analysis of this algorithm in terms of convergence rate and error bounds (when it is used in an approximate form). I will discuss these results with respect to state of the art results about Value Iteration and Policy Iteration.

In their original paper, Bertsekas and Ioffe applied an approximate version of this algorithm to the game of Tetris. I will revisit this application and report empirical results that are less ``intriguing'' than originally reported, and suggest an explanation for the difference. Eventually, I will present some general ideas that we have used in order to improve the performance on this application.

Retour à la liste des séminaires

Deux sujets sont abordés : les G-graphes, ou l'aspect géométrique des groupes et HLC, ou l'aspect géométrique des images appliqué à la compression.

Introduits en 2003, les G-graphes sont d'abord conçus pour l'étude du problème d'isomorphisme de graphe et sont proches des graphes de Cayley. Il s'agit de graphes élaborés à partir de groupes et dont on contrôle en partie le comportement du groupe d'automorphisme. La construction des G-graphes est d'abord abordée, ainsi que leurs propriétés élémentaires. La classification des graphes symétriques est ensuite attaquée. Avec les G-graphes le Foster Census, le catalogue des graphes cubiques symétriques, peut être étendu considérablement et généralisé au cas des graphes quintiques, symétriques ou semisymétriques.

Une représentation géométrique des images est introduite, basée sur des hypergraphes de rectangle. Cette représentation donne un algorithme de compression sans pertes très efficace sur les images synthétiques et appelé HLC. HLC se combine efficacement avec un algorithme de compression de données génériques, en l'occurrence PPMd, choix que justifié par une étude empirique. Des résultats expérimentaux sont finalement fournis ainsi que la généralisation de la technique aux images 3D et à la compression presque sans pertes.

Retour à la liste des séminaires

Our goal is to find an approximate shortest path for a point robot moving in a planar subdivision. Distances in each face of this subdivision are measured by a convex distance function. Different convex distance functions may be used for different faces, and obstacles are allowed. We give applications to two special cases: the weighted region problem, and motion planning in the presence of uniform flows. This is joint work with Siu-Wing Cheng, Hyeon-Suk Na, and Yajun Wang

Retour à la liste des séminaires

Les avancées récentes en matière de réseaux de communications ont grandement contribué au développement des grilles de calcul à grande échelle. Mais cette évolution matérielle implique une modification importante des modèles algorithmiques classiquement utilisés en parallélisme pour utiliser efficacement ces nouveaux systèmes. Cet exposé propose un survol de mes différents travaux dans ce domaine. Ces travaux portent essentiellement sur deux aspects. Le premier concerne les environnements haut niveau permettant une exploitation efficace de ces systèmes. Je présenterai notamment ma contribution au développement de l'intergiciel Diet.

Le second se situe au niveau algorithmique avec l'étude et le développement d'algorithmes parallèles itératifs asynchrones pour le calcul scientifique sur ces grilles. Je présenterai mes contributions à ces algorithmes dans les cadres discret et continu. Des bilans seront dressés pour chaque thème abordé.

Retour à la liste des séminaires

Mardi 17 avril, A006, 16h30
Csaba Toth, MIT
Extremal problems on simplices spanned by a finite point set in Euclidean space

Given an equivalence relation on finite point configurations, a typical Erd\H{o}s-type question asks the maximum size $f_d(n)$ of an equivalence class and the minimum cardinality $g_d(n)$ of distinct equivalence classes determined by $n$ points in $d$-space. This family of problems found applications in range counting, pattern recognition, data compression, and motion planning. In this talk, the finite point configurations are simplices, and two simplices are considered to be equivalent if they have the same volume. It turns out that these questions can be reduced to problems on the number of incidences between points and surfaces in Euclidean space. I will present new upper and lower bounds for these problems.

First I show a tight bound of $O(n^d)$ on the number of full dimensional simplices of minimum nonzero volume determined by $n$ points in $d$-space, and show that all such simplices can be reported in $O(n^d)$-time. In three dimensions, every $n$-element point set determines at most $O(n^{7/2})$ tetrahedra of unit volume, and there are $n$ points that determine at least $\Omega(n^3 \log \log{n})$. The number of distinct volumes of the tetrahedra spanned by $n$ non-coplanar points in 3-space is at least $\Omega(n)$, which is best possible apart from the constant factor. This answers an old question of Erd\H{o}s, Purdy, and Straus. I also discuss analogous problems for triangles in 3-space; and conclude with related open problems.

(Joint work with Adrian Dumitrescu.)

Retour à la liste des séminaires

Jeudi 29 mars, C05, 14h
Mohamed Tajine, LSIIT, Université de Strasbourg
Reconstruction d'informations qualitatives et quantitatives en imagerie : illustration sur la topologie et la mesure de longueur en dimension 2

Je commencerai mon exposé par une présentation de la discrétisation de Hausdorff puis j'expliquerai comment reconstruire les topologies de certains objets euclidiens en 2D à partir de leurs discrétisations de Hausdorff. Plus précisément, je montrerai que si un objet est régulier (c'est-à-dire que son bord vérifie certaines propriétés de différentiabilités) alors sa topologie peut être calculée à partir d'une de ses discrétisations de Hausdorff si la résolution de l'espace discret est inférieur à une borne dépendant de la régularité de l'objet en question.

Je présenterai ensuite quelque résultats en relation avec l'estimation de longueur à partir des discrétisations. Je montrerai en particulier que les estimateurs locaux ne convergent presque jamais.

Retour à la liste des séminaires

Jeudi 8 mars, B11, 15h
Sang Won Bae, KAIST, Corée du Sud
Proximity and Location Problems on Transportation Networks

On our planet, human beings have been developing many kinds of transportation for faster movement and communication. Although these facilities are of course for reducing time duration during movement among societies, in many cases we don't know the best way to use (or construct) them.

First of all, we consider 'shortest travel times' rather than 'geographic distances.' The shortest travel time is induced by a transportation network, which describes a 'real' transportation network by a plane graph with speeds on its edges. Along the network, travelers move at the specified speed; otherwise at the unit speed. Under this setting, the shortest travel time among all possible paths connecting two points induces a metric on the plane. Thus, the goal of this talk is to introduce this new metric and related problems, which are solved, on-going, or open, or even totally undefined.

This talk has two parts. First part of the talk is devoted to Voronoi diagrams with respect to the shortest travel time metric: With a history of the problem, recent results and some open issues are presented. Second part of the talk briefly deals with location problems related to transportation networks, which include furthest Voronoi diagrams, constructing optimal highways, and so on.

Retour à la liste des séminaires

Lundi 5 mars, C005, 10h30
Damien Regnault, LIP, ENS Lyon
Une étude de l'automate cellulaire Minorité 2D probabiliste : Porter des rayures est-il une fatalité pour les snobs?

Les automates cellulaires sont ordinairement associés à une dynamique synchrone et déterministe, leurs versions asynchrones ou probabilistes ont été beaucoup moins étudiées bien qu'elles soient utiles pour la modélisation. L'étude de la dynamique asynchrone est d'autant plus nécessaire car leurs comportements en dynamique asynchrone sont radicalement différents de leurs comportements synchrones.

Dans cet exposé, nous présentons une analyse d'un automate cellulaire en deux dimensions, 2D Minorité, en dynamique totalement asynchrone, où seulement une cellule se met à jour à chaque pas de calcul. Cet automate cellulaire est utile en informatique, en biologie ou en science sociale par exemple, et présente une grande variété de comportements bien que la règle de transition semble simple. En particulier, nous avons constaté l'émergence de motifs rayés, qui sont courants, selon des simulations, chez d'autres automates cellulaires importants, comme le jeu de la vie.

Dans cet exposé, nous allons présenter une analyse mathématique des premières et dernières étapes de l'automate minorité 2D en dynamique asynchrone. Nos résultats sont basés sur la définition d'une énergie d'interaction et reposent sur une analyse de la dynamique des frontières entre différentes régions qui rentrent en compétition. Nos résultats sont une première étape vers une analyse complète de cet automate cellulaire probabiliste. Beaucoup de questions restent ouvertes : en particulier décrire mathématiquement le milieu de l'évolution de Minorité 2D où de nombreuses régions rivalisent les unes avec les autres, ou définir des paramètres (énergie, frontières, ...) pour d'autres automates (par exemple le jeu de la vie) qui présentent en comportement asynchrone des similarités avec Minorité 2D.

Retour à la liste des séminaires

Jeudi 1 mars, A006, 14h
Marie-Andrée Da Col, LSIIT, Strasbourg
Plans et applications affines discrètes

Mon intervention se déroulera en 2 parties. Dans la première partie je m'intéresserai aux plans discrets et particulièrement aux configurations locales dans ces plans. Je parlerai donc des (m;n)-cubes, du nombre de (m;n)-cubes distincts dans un plan mais également de leur relation avec les "ombrelles" (définies par J. Françon). Dans la deuxième partie je parlerai d'AQA (applications quasi-affines), je reviendrai assez rapidement sur la définitions et quelques propriétés, en développant un peu plus les proriétés liant les AQAs aux droites et plans discrets.

Retour à la liste des séminaires

Mardi 20 fevrier, B11, 15h30
Mohab Safey El Din, LIP6 Universite Paris 6, INRIA Rocquencourt, projet SALSA
Algorithmes efficaces pour décider des conditions de signe satisfaites par un polynôme en plusieurs variables.

Soit $f\in \Q[X_1, \ldots, X_n]$ un polynôme de degré $D$, $S\subset \R^n$ l'ensemble semi-algébrique défini par $f >0$ et $V$ l'ensemble algébrique réel défini par $f=0$. Dans cet exposé, on montrera comment ramener le calcul d'au moins un point par composante connexe de $S$ au calcul d'au moins un point par composante connexe d'un ensemble algébrique réel défini par une équation. Cette réduction se fait par un calcul efficace de {\em valeurs critiques généralisées} qu'on détaillera. Une fois ce pré-calcul effectué, on verra alors comment calculer au moins un point par composante connexe dans un ensemble algébrique réel tel que $V$, défini par une équation polynomiale. La complexité théorique de ces algorithmes est simplement exponentielle en le nombre de variables et les implantations que nous en avons faites permettent de résoudre des problemes qui sont hors d'atteinte des méthodes précédentes.

Retour à la liste des séminaires

Vendredi 16 février, A006, 14h
Benoît Naegel, EIG-HES (Ecole d'Ingénieurs de Genève)
Morphologie mathématique et imagerie médicale: contributions théoriques et applicatives.

La morphologie mathématique, discipline introduite originellement par Matheron et Serra en 1964, a connu depuis 40 ans des développements théoriques très riches et représente actuellement une branche fondamentale de l'analyse d'images. Cette approche est particulièrement bien adaptée à la nature discrète des images numériques et représente une alternative aux approches continues dérivées du traitement du signal. Dans le cas d'applications réelles, et en particulier dans le domaine de l'imagerie médicale, il est cependant nécessaire d'intégrer ces opérateurs dans des processus de plus haut niveau. Dans cet exposé nous décrirons quelques méthodes permettant d'intégrer de la connaissance a priori dans les opérateurs de morphologie mathématique et nous montrerons des exemples d'applications dans le domaine de l'imagerie médicale.

Dans une première partie, nous exposerons brièvement les notions fondamentales de la morphologie mathématique, les opérateurs connexes, l'arbre des composantes ainsi que le paradigme de segmentation morphologique. Dans une seconde partie, nous aborderons les moyens de modéliser et d'utiliser de la connaissance a priori pour guider des processus de segmentation et de détection de structures d'intérêt. En particulier, nous décrirons la classe des opérateurs d'intervalle (transformée en tout-ou-rien) appliquée aux images à niveaux de gris. Nous aborderons également la notion de filtrage d'attributs ainsi que le principe original d'apprentissage à partir de l'arbre des composantes. Dans une troisième partie, nous montrerons des exemples d'application dans le cadre de l'imagerie médicale: segmentation des organes, du réseau vasculaire hépatique et des vertèbres à partir d'images scanners 3D, détection de grains de beauté à partir de photographies numériques du corps entier.

Retour à la liste des séminaires

Vendredi 8 février, A006, 14h
Lionel Eyraud-Dubois, ENS-Lyon
Analyse d'algorithmes d'ordonnancement en présence de réservations

Nous nous intéressons au problème d'ordonnancement d'un ensemble de tâches parallèles indépendantes sur une machine parallèle homogène. Ce problème a été largement étudié d'un point de vue théorique (analyse de complexité, performance et garantie des algorithmes), mais aussi d'un point de vue pratique (ordonnanceurs dans les systèmes de production). Certains de ces ordonnanceurs permettent de réserver quelques processeurs d'une grappe à l'avance, les rendant alors indisponibles. Ces réservations représentent des quantités de ressources assignées, un certain temps à l'avance, à des applications spécifiques.

Retour à la liste des séminaires

Mardi 6 Février, Amphi, 14h
J. Rossignac, Georgia Institute of Technology, USA
Shape Comparison, Simplification, and Compression

How to measure and visualize the discrepancy between two or more shapes? How to optimize the deformation that morphs between two given shapes? How to simplify a shape by removing small or sharp features without altering the regular portions? How to compute the control mesh of a subdivision surface that approximates a given shape? How to compress and decompress such a control mesh? How to recover its sharp edges? The speaker will discuss the relations between these questions and propose some answers.

References:

Chazal,F., Lieutier,A. , Rossignac,J., Whited,B.: Ball-map: Homeomorphism between compatible surfaces, GVU Tech Report GIT-GVU-06-05.

Williams,J., Rossignac,J.: Tightening: Curvature-Limiting Morphological Simplification. ACM Symposium on Solid and Physical Modeling (SPM). 2005.

Williams,J., Rossignac,J.: Mason: Morphological Simplification, Graphical Models, 67(4)285:303, 2005.

Attene,M., Falcidino,B., Spagnuolo,M. , J. Rossignac,J.: Sharpen&Bend: Recovering curved edges in triangle meshes produced by feature-insensitive sampling, IEEE Transactions on Visualization and Computer Graphics (TVCG), vol 11, no 2, pp 181-192, March/April 2005.

Retour à la liste des séminaires

Mardi 6 Février, A006, 10h30
Fanny Pascual , ID-IMAG , Grenoble
Ordonnancement de tâches détenues par des utilisateurs individualistes

Cet exposé se place dans le cadre de la conception de protocoles devant interagir avec des utilisateurs indépendants et individualistes. Chaque utilisateur souhaite optimiser sa propre fonction objectif, qui peut être très différente de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser cette fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste.

Je présenterai dans cet exposé un problème d'ordonnancement dans lequel des utilisateurs individualistes sont en concurrence pour des ressources partagées : chaque utilisateur possède une tâche dont il souhaite qu'elle soit effectuée le plus rapidement possible. Les utilisateurs utilisent alors leur liberté d'action (déclaration du temps d'exécution de leur tâche, choix de la machine sur laquelle leur tâche sera exécutée, etc.) afin de minimiser la date à laquelle leur tâche a été effectuée. Nous étudions alors les conséquences que ce comportement peut avoir sur la qualité de l'ordonnancement retourné.

Retour à la liste des séminaires

Jeudi 18 janvier, A006, 11h
Elias P. Tsigaridas, Loria, Vegas
Computations with real algebraic numbers and applications to computational geometry

Real algebraic numbers are the numbers that are real solutions of a univariate polynomial with integer coefficients. We present algorithmic and complexity results about exact algorithms for computations with real algebraic numbers and applications of these algorithms to non-linear computational geometry.

We represent the real algebraic numbers using the isolating interval representation, i.e a square-free polynomial and an isolating interval. In order to construct a real algebraic number we need to isolate the real roots of univariate polynomial. We will present in a unified way the subdivision algorithms, namely Sturm, Descartes and Bernstein and also the CF algorithm which is based on the continued fraction expansion of the real numbers. Using projection we extend the real solving algorithms to bivariate polynomial systems.

As for the computations that involve one or two real algebraic numbers, we consider comparison, sign evaluation and the problem of simultaneous inequalities. For these computations we exploit the Sturm-Habicht sequences.

For all the previous computations, when the degree the univariate polynomials is $\leq 4$ and/or the total degree of the bivariate polynomials is $\leq 2$ we present special purpose algorithms with constant time arithmetic complexity.

We will use the previous algorithms in order to tackle the predicates needed in some problems of (non-linear) computational geometry. We will consider the problems of the arrangement of conics arcs and curves in the plane and the Voronoi diagram of ellipses.

Finally, we consider algorithms that given a convex lattice polygon test whether it can be decomposed into a Minkowski sum of two other such polygons and if so, find one or all such decompositions. The problem is closely related to the problem of bivariate polynomial factorization.

Retour à la liste des séminaires

Jeudi 11 janvier, B13, 10h30
Martine Dexet, LIRMM, Montpellier
Une préimage généralisée pour la reconnaissance et la reconstruction d'objets discrets

Depuis plusieurs années, des travaux portant sur la reconnaissance et la reconstruction d'objets discrets utilisent la dualité, et se fondent notamment sur la notion de préimage. Dans cet exposé, nous définissons tout d'abord une nouvelle préimage, appelée préimage généralisée, qui permet de déterminer l'ensemble des hyperplans coupant un ensemble de polytopes donnés. A partir de cette préimage, nousprésentons un algorithme de reconnaissance de primitives discrètes en dimension quelconque, et l'appliquons dans le cadre des modèles de discrétisation Supercouverture et Standard. Nous décrivons ensuite deux algorithmes de reconstruction d'objets discrets en dimensions 2 et 3. Ces deux algorithmes fournissent en particulier une reconstruction inversible pour le modèle Standard. Les divers algorithmes présentés ont été mis en oeuvre au sein d'un logiciel de modélisation d'objets géométriques. Ce logiciel présente la particularité d'autoriser la manipulation d'objets représentés tant sous forme discrète que continue. Nous terminons cet exposé en présentant succintement cet outil.

Retour à la liste des séminaires

2006

Jeudi 5 octobre, B13, 10h30
Valérie Berthé, CNRS, LIRMM, Montpellier
Géométrie discrète et combinatoire des mots

Le but de cet exposé est d'illustrer les interactions naturelles qui existent entre combinatoire des mots et géométrie discrète arithmétique à travers plusieurs discrétisations d'objets ou de transformations classiques en géométrie euclidienne (droites, plans, rotations). Nous montrerons comment des techniques issues de la dynamique symbolique, et appliquées à des codages de telles discrétisations, permettent d'obtenir des résultats sur l'énumération de configurations locales et sur leurs propriétés statistiques.

Retour à la liste des séminaires

This talk will present software being developed for computing exact arrangements of spheres in three dimensions. Arrangements of spheres are a logical next step both since they have a number of applications (for example computation of potentials in molecular biology applications) and since they are the simplest curved objects in three dimensions. The software sweeps out a novel decomposition of the arrangement which has simple cells, but avoids needing to deal with algebraic numbers of degree higher than two. In the talk I will discuss the decomposition, the set of predicates used and algebraic issues encountered.

Joint work with Monique Teillaud.

Retour à la liste des séminaires

Vendredi 9 juin, A006, 14h
Emmanuelle Lebhar, LIP, ENS Lyon
``Un seuil de Theta(loglog n) sur la dimension doublante pour la navigabilite des graphes augmentes" ou "On ne peut pas tout petit-mondiser''

Kleinberg a montre comment augmenter les grilles par des liens aleatoires de facon a ce qu'elles deviennent navigables; c'est-a-dire que le routage glouton calcule des chemins de longueur polylogarithmique en esperance entre toute paire de noeuds. Cela conduit a la question cruciale de determiner si une telle augmentation est possible pour tout graphe. Dans cet article, nous repondons negativement a cette question en exhibant un seuil sur la dimension doublante, au-dessus duquel une famille infinie de graphes ne peut pas etre augmentee pour devenir navigable, quelle que soit la distribution de liens. Precisement, il etait connu que les graphes de dimension doublante au plus O(loglog n) sont navigables. Nous montrons que pour une dimension doublante >> loglog n, une famille infinie de graphes ne peut etre augmentee pour devenir navigable. Notre preuve repose sur un argument combinatoire. Enfin, nous completons notre resultat en etudiant les grilles que nous demontrons pouvoir toujours etre augmentees pour devenir navigables.

Retour à la liste des sémin\ aires

Jeudi 23 mars, A008, 14h
Damien Jamet, LORIA, Adagio
Combinatoire des mots en géométrie discrète

Les travaux présentés dans cet exposé se situeront au carrefour de la géométrie discrète et de la combinatoire des mots. Je m'intéresserai en particulier aux relations entre ces disciplines et montrerai, comment obtenir de nombreuses propriétés (propriétés structurelles, statistiques...) des plans et surfaces discrets (analogues discrets des plans et des surfaces usuels) à partir d'un codage des ces objets par des mots bidimensionnels indexés par Z2. Je terminerai mon exposé par l'énoncé de quelques perspectives de recherches ainsi que quelques questions ouvertes auxquelles je m'intèresse actuellement.

Retour à la liste des séminaires

Jeudi 6 avril, A006, 16h
Marc Pouget, Freie Universitat, Berlin
Ridges and umbilics of polynomial parametric surfaces

Given a smooth surface, a blue (red) ridge is a curve along which the maximum (minimum) principal curvature has an extremum along its curvature line. Ridges are curves of extremal curvature and therefore encode important informations used in segmentation,registration, matching and surface analysis.

State of the art methods for ridge extraction either report red and blue ridges simultaneously or separately --in which case need a local orientation procedure of principal directions is needed, but no method developed so far topologically certifies the curves reported.

First, for any smooth parametric surface, we exhibit the implicit equation P=0 of the singular curve P encoding all ridges of the surface (blue and red), and analyze its singularities.

Second, for a polynomial surface this equation defines an algebraic curve. We develop the first certified algorithm to produce a topologically certified approximation of the curve P. The algorithm exploits the singular structure of P --umbilics and purple points, and reduces the problem to solving zero dimensional systems using Rational Univariate Representations and isolate roots of univariate polynomials. An experimental section illustrates the efficiency of the algorithm on a Bezier patch.

Retour à la liste des séminaires

Vendredi 10 mars, B13, 14h.
Nicolas Passat, ESIEE, Noisy-le-Grand
Analyse des structures vasculaires cérébrales obtenues en IRM. Guidage d'approches discrètes par connaissance anatomique.

L'analyse par les radiologues des ARM (angiographies par résonance magnétique) cérébrales est une tâche ardue en raison du volume des données à traiter et du nombre croissant d'examens réalisés. La création de méthodes de segmentation des vaisseaux cérébraux à partir de telles images constitue donc un domaine de recherche répondant à un besoin réel.

Les travaux présentés sont dédiés au développement de telles méthodes. L'effort y est notamment focalisé sur la capacité à adapter leur comportement aux images traitées et à leur charge sémantique. Ce concept d'adaptativité est mis en oeuvre au travers de l'intégration de connaissance anatomique de haut niveau qui a pour but de guider des outils de traitement d'image.

La formalisation et l'intégration de connaissance sont abordées au travers du concept d'atlas vasculaires cérébraux. La segmentation des images est quant à elle considérée dans le cadre d'une méthodologie discrète, basée sur les concepts fondamentaux de morphologie mathématique, de géométrie et de topologie discrètes.

Globalement, ces travaux se présentent comme une (modeste) introduction à une méthodologie de segmentation des structures vasculaires relativement nouvelle dans la mesure où elle tend à associer le potentiel des outils de traitement d'image actuels avec l'approche par apprentissage et utilisation de connaissances qui est généralement l'apanage des spécialistes humains.

Retour à la liste des séminaires

Jeudi 19 janvier, B13, 11h
Andreas Holmsen, Université de Bergen, Norvège
Encoding of families of convex sets in the plane

We describe a combinatorial encoding of planar families of convex sets which generalizes the notion of allowable sequences which encode finite point sets in the plane. We also discuss some combinatorial problems concerning planar families of convex sets and how they translate into our model.

Retour à la liste des séminaires

Jeudi 26 janvier, B200, 11h
Mira Lee, KAIST University, Corée du Sud
Maximally repeated sub-patterns of a point set

Let S be a set of n points in R^d. A subset of S is a repeated sub-pattern if it can be translated to another subset of S. A sub-pattern P is maximally repeated if it cannot be extended without losing at least one of its occurrences. The number of maximally repeated sub-patterns of a set of n points was conjectured to be polynomial. We show that this number is in fact Theta(2^n/2) in the worst case, regardless of the dimension d.

Retour à la liste des séminaires

Mercredi 18 janvier, A006, 16h
Hyeon-Suk Na, Université Soongsil, Coree du Sud
Optimal prefix coding restricted in a language

In the talk, we discuss the problem of constructing minimum-cost prefix-free codes for equiprobable words under the assumption that all codewords are restricted to belonging to some language L. We examine how, given certain types of L, the structure of the minimum-cost code changes as the number of codewords grows.

Retour à la liste des séminaires

Jeudi 2 février, B11, 14h
Stephane Gobron, IUT St-Die-des-Vosges
Simulations de phénomènes naturels à base d'automates cellulaires

Depuis le début des années 90, un certain nombre de phénomènes naturels ont été proposés via des modèles basés ou non sur des modèles physiques. Les résultats, principalement relatifs à des effets de surface [Dorsey96, Merillou01, Desbenoit04], étaient souvent impressionnants.

Toutefois, aussi réalistes soient-ils, aucun d'entre eux ne traite du problème de la génération et de l'interaction entre phénomènes. En effet, comment simuler des scènes vraiment réalistes présentant une combinaison d'effets ? L'illustration suivante résume le problème : suite à l'érosion d'une surface une fissure se propage, engendrant de l'écaillage et/ou pelage de la couche extérieure, ce qui permet des effets de patine sur la couche métallique intérieure et parallèlement provoque de nouveaux effets d'érosion puis de sédimentation des métaux oxydés. Il est difficile de concevoir le modèle global d'un tel phénomène pourtant si commun.

Pour résoudre ce problème, au lieu de se focaliser à simuler un comportement global nous proposons l'approche inverse. Il s'agit de modéliser des comportements locaux au travers de leur nature : des états et des règles de comportement qui synchronisent les changements de ces états. C'est ce que définissent les automates cellulaires (AC). L'étude n'est pas nouvelle [Conway70] et montre un certain nombre de problèmes non triviaux, et notamment l'imprédictibilité de convergence des AC.

Cet exposé présente différentes solutions [Gobron99, Gobron01, Devillard05, Even05] que nous avons élaborées et validées au travers de cas concrets.

Retour à la liste des séminaires

Vendredi 13 janvier, B11, 14h
Otfried Cheong, KAIST Corée du Sud
On Shortest Approximation of Closed Convex Curves

Given a convex curve C and a parameter delta > 0, we consider the problem of finding the shortest delta-approximation H of C, that is, the shortest curve H such that for every point x in C there is a point y in H with d(x,y) <= delta. We characterize the optimal solution under certain restrictions on C.

Retour à la liste des séminaires

Jeudi 5 decembre, A006, 13h45
Siu-Wing Cheng, HKUST Hong-Kong
Sampling and Meshing a Surface with Guaranteed Topology and Geometry

We present an algorithm for sampling and triangulating a smooth surface S in R³ where the triangulation is homeomorphic to S. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely computations of the intersection points of a line with the surface and computations of the critical points of a natural height function defined on the surface and its restriction to a plane. The algorithm ensures bounded aspect ratio, size optimality, and smoothness of the output triangulation. Unlike previous algorithms, this algorithm does not need to compute the local feature size for generating the sample points which was a major bottleneck. Experiments show the usefulness of the algorithm in remeshing and meshing CAD surfaces that are piecewise smooth

Retour à la liste des séminaires

2005

Jeudi 8 décembre, A208, 16h
Y. Kenmochi , CNRS/ESIEE/Université de Marne-la-Vallée
Étude de frontières d'objets discrets et de surfaces discrètes pour l'analyse de formes 3D

Pour définir les frontières d'objets discrets ainsi que les surfaces discrètes sans contradiction topologique, nous proposons une méthode qui définit une topologie sur un espace pour une image numérique en trois dimensions par une approche basée sur les complexes polyédraux. En utilisant cette théorie, nous proposons un algorithme d'extraction de frontières d'objets discrets, dans lequel les frontières sont définies comme des surfaces combinatoires (des surfaces divisées en triangles dont les sommets sont des points discrets).

Notre objectif est de pouvoir analyser de telles surfaces en nous basant sur une méthode de géométrie différentielle discrète. En étudiant les courbures Gaussiennes discrètes calculées en chaque sommet de la surface combinatoire, nous proposons des caractérisations locales de formes sur notre surface et montrons aussi que nous pouvons énumérer toutes les configurations locales de ces surfaces combinatoires qui ont des formes différentes. Enfin, nous illustrons dans cet exposé l'intérêt de notre approche dans le contexte de l'analyse de formes 3D, en présentant quelques exemples d'application, par exemple, la reconnaissance des plans discrets.

Retour à la liste des séminaires

Vendredi 2 decembre, B11/13, 11h
Damien Stehlé, Soutenance de thèse, LORIA, Spaces
Algorithmique de la reduction de reseaux et application a la recherche de pires cas pour l'arrondi de fonctions mathematiques

Les réseaux euclidiens sont un outil particulièrement puissant dans plusieurs domaines de l'algorithmique, en cryptographie et en théorie algorithmique des nombres par exemple. L'objet du présent mémoire est dual: nous améliorons les algorithmes de réduction des réseaux, et nous développons une nouvelle application dans le domaine de l'arithmétique des ordinateurs. En ce qui concerne l'aspect algorithmique, nous nous intéressons aux cas des petites dimensions (en dimension un, ou il s'agit du calcul de pgcd, et aussi en dimensions 2 a 4), ainsi qu'a la description d'une nouvelle variante de l'algorithme LLL, en dimension quelconque. Du point de vue de l'application, nous utilisons la méthode de Coppersmith permettant de trouver les petites racines de polynômes modulaires multivariés, pour calculer les pires cas pour l'arrondi des fonctions mathématiques, quand la fonction, le mode d'arrondi, et la précision sont donnes. Nous adaptons aussi notre technique aux mauvais cas simultanés pour deux fonctions. Ces deux méthodes sont des pré-calculs coûteux, qui une fois effectues permettent d'accélérer les implantations des fonctions mathématiques élémentaires en précision fixée, par exemple en double précision.

La plupart des algorithmes décrits dans ce mémoire ont été valides expérimentalement par des implantations, qui sont disponibles sur ma page web.

Retour à la liste des séminaires

Jeudi 1 décembre, A006, 16h
Wan-Chiu Li, LORIA, Alice
Automatic mesh to T-spline surface conversion

In this work, we propose a method which automatically converts a polygonal mesh to the spline surfaces. The main contributions of this work are:

1. An automatic procedure to convert a triangulated mesh to spline surfaces is proposed.

2. It mimics the chartification process of the conversion done by a human designer by aligning the edges of the quadrilateral charts along the two principle curvature directions of the model.

3. The output of the conversion is compatible with the commercial T-spline product for Maya.

Retour à la liste des séminaires

Let G=(V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A rectilinear dual of G is a partition of a rectangle into |V| simple rectilinear regions, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge in E. A rectilinear dual is called a cartogram if the area of each region is equal to the weight of the corresponding vertex. We show that every vertex-weighted plane triangulated graph G admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant.

Joint work with Mark de Berg and Elena Mumford

Retour à la liste des séminaires

Mercredi 8 novembre, B013, 14h
M. Grabisch, Université Paris I - Panthéon-Sorbonne - et Paris 6 (LIP6)
Capacités, intégrale de Choquet et leurs applications en classification

Les capacités introduites par Choquet en 1953 (également nommées mesures floues, mesures non-additives) constituent une généralisation de la notion de mesure classique (mesure de probabilité). L'intégrale de Choquet qui leur est associée est une généralisation de l'intégrale de Lebesgue, et peut être vue comme une façon de calculer une espérance mathématique plus générale. D'un point de vue applicatif, on peut distinguer deux interprétations différentes d'une capacité : une représentation d'un degré d'incertitude d'un événement, ou une modélisation de l'importance ou pouvoir d'une coalition d'éléments (critères, attributs, joueurs, votant, etc.). C'est cette dernière interprétation qui sert en classification et en décision multicritère, car elle permet de modéliser l'importance des attributs en classification. Dans un problème pratique se pose toujours la question de l'identification ou apprentissage de la capacité modélisant le problème en question. Nous présentons les diverses méthodes pour résoudre cette question. Enfin, une capacité assignant un degré d'importance à chaque coalition d'attributs, se pose le problème de savoir quelles sont les importances individuelles de chaque attribut, et s'il y a des phénomènes d'interaction entre les attributs. Nous proposons une définition générale d'indice d'interaction entre attributs, ainsi qu'un indice d'importance.

Retour à la liste des séminaires

Jeudi 6 octobre, A208, 16h45.
Bertrand Kerautret, LORIA, Adage
Reconstruction et lissage de surfaces discrètes.

Dans une première partie de cet exposé nous présenterons une approche discrète de reconstruction de surfaces basée sur l'utilisation de contraintes géométriques et photométriques contenues dans une ou plusieurs images. Cette approche permet de définir des contraintes explicites pour lever l'ambiguïté concave/convexe, en particulier lors de l'utilisation d'une source lumineuse orientée dans la direction d'observation. Cette méthode a pu montrer des résultats robustes à la fois par rapport au modèle de réflectance pouvant être spéculaire mais aussi par rapport au bruit. Nous présenterons ensuite une application originale de ces résultats pour la création et l'édition d'une forme en trois dimensions à partir de plusieurs dessins.

Dans une deuxième partie, nous présenterons une nouvelle approche réversible de lissage de surfaces discrètes. Cette méthode est basée sur l'estimation des caractéristiques du plan discret à partir d'un critère statistique et géométrique. Ces caractéristiques nous permettent de définir une surface à partir de la projection des points discrets sur le plan tangent. La nouvelle surface Euclidienne peut être utilisée pour l'extraction de paramètres géométriques et pour la visualisation, tout en étant sans perte d'information par rapport à la surface discrète initiale.

Retour à la liste des séminaires

Jeudi 29 septembre, B11, 16h45.
Xavier Goaoc, LORIA, Vegas
Combien de convexes faut-il pour fixer une droite ?

Résumé : Une droite est fixée par une famille d'objets si elle les coupe tous et que dès qu'on la perturbe elle ne coupe pas au moins l'un d'entre eux -- autrement dit, si elle est un point isolé de l'ensemble des droites intersectant tous ces objets.

Pour toute famille de convexes du plan fixant une droite, il existe une sous-famille de 3 convexes qui suffit à la fixer (Hadwiger, 1957). Dans cet exposé je présenterai quelques résultats récents sur le nombre d'objets de l'espace suffisant pour fixer une droite.

Retour à la liste des séminaires

Jeudi 15 septembre, A006, 16h45.
Théo Papadopoulo, INRIA Sophia-Antipolis projet Odyssee
Calcul de l'activité électrique du cerveau par MEEG.

Résumé : L'électro- et la magnéto-encéphalographie sont deux techniques relativement récentes pour mesurer l'activité électrique du cerveau. Ces méthodes ont la propriété de permettre une très bonne résolution temporelle. Le projet Odyssée a developpé depuis quelques années plusieurs méthodes de reconstruction de type "imagerie" par problèmes inverses. Différents aspects liés à ce problème de reconstruction seront (brièvement) considérés:
- calcul de la géométrie de la tête à partir d'images IRM anatomiques.
- problèmes liés aux conductivités et à leur modélisation.
- problèmes directs et inverses MEEG en surfacique et volumique.

Retour à la liste des séminaires

Mardi 13 septembre, A006, 16h45.
Jean Ponce, Ecole Normale Superieure et University of Illinois
Photographie 3D

Résumé : Cette présentation est consacrée à l'acquisition automatique de modèles infographiques réalistes d'objets et de scènes à partir de données images ("photographie 3D"). Je présenterai un cousin de la conique absolue de Chasles, le complexe quadratique absolu, et discuterai son application à l'étalonnage de caméras dont les pixels sont rectangulaires ou carrés. Je présenterai également un nouvel algorithme qui utilise les contraintes géométriques et photométriques associées avec plusieurs images prises par des caméras étalonnées pour construire des modèles solides de bonne qualité d'objets dont la forme peut être très compliquée. Je conclurai par une brève discussion de travaux récents dans le domaine de la reconnaissance d'objets. Les transparents.

Retour à la liste des séminaires

Mercredi 22 juin, B13, 11h
Benjamin Werner, INRIA-Futurs et LIX
A propos de la preuve formelle du théorème des quatre couleurs

Je vais essayer de présenter quelques aspects de la récente preuve en Coq du théorème des quatre couleurs. En particulier de l'exploitation de résultats calculatoires à l'intérieur du raisonnement mathématique.

Retour à la liste des séminaires

Mardi 24 mai, B13, 16h
Dave Bremner, University of New Brunswick, Canada
Primal-Dual methods for data depth

A common task in e.g. computational statistics is to compute a "centre" of a cloud of set of vectors. The naive centre of a set of vectors is the coordinate-wise average or barycenter. While trivial to compute, it is extremely non-robust, since one erroneous vector can destroy any information content. The Tukey median is the point (or points) of maximum "halfspace depth", a measure of how many data points are outside the minimizing halfspace containing a candidate centre. The Tukey median is much more robust than the barycentre , but is difficult to compute both in theory and in practice. In this talk I will describe some work on algorithms and software for computing halfspace depth. These "primal-dual" techniques have the useful property that at every stage they maintain an upper and lower bound on the final answer, and thus provide the user with a partial solution even when terminated early.

This talk describes joint work with Komei Fukuda (ETH Zuerich) and Vera Rosta (McGill University).

Retour à la liste des séminaires

Jeudi 19 mai, A006, 16h
Olivier Devillers, INRIA Sophia Antipolis (Geometrica)
Représentation compacte de triangulations

Nous considérons le problème de représenter des structures géométriques de manière compacte en gardant une implémentation efficace des opérations de navigation. Pour le cas des triangulations planaires à m faces, nous proposons une représentation compacte de l'information combinatoire qui améliore à 2.175 bits par triangle le coût asymptotique en espace et qui permet la navigation entre triangles adjacents en temps constant. Pour les triangulations à m faces d'une surface de genre g, notre représentation nécessite asymptotiquement de 36(g-1)lgm bits supplémentaires. La structure permet aussi l'accès en temps constant des informations associées aux sommets, notamment leurs coordonnées, cependant nous ne traitons pas ici la compression de cette information géométrique. (RR INRIA 5433.)

Retour à la liste des séminaires

Mardi 5 Avril, B11, 14h30
Frederic Sur, Loria (Modbio)
Décision a contrario pour la reconnaissance de formes

Nous proposons une méthode de reconnaissance des formes géométriques dans les images numérique, dans un cadre générique dans lequel aucun modèle sur les formes cherchées n'est disponible, ni aucune connaissance a priori (contrairement à la reconnaissance bayésienne par exemple). L'originalité de notre approche réside dans le fait qu'elle n'est pas spécifique à une application particulière. Nous expliquons comment apparier des formes, puis comment identifier des groupements de formes dans le cadre de la classification non supervisée. Le point commun à ces travaux est la "décision a contrario" : un événement est déclaré significatif s'il est peu probable de l'observer par hasard. Cette méthode permet une décision sans paramètre fixé par l'utilisateur grâce à des arguments statistiques.

En collaboration avec Pablo Musé, Julie Delon, Jean-Michel Morel (CMLA, ENS de Cachan), Frédéric Cao (Vista, IRISA) et Yann Gousseau (TSI, ENST).

Retour à la liste des séminaires

Jeudi 24 mars, B13, 16h
Monique Teillaud, Inria Sophia-Antipolis
Arrangement de quadriques dans R³

Nous présentons un algorithme de balayage pour le calcul d'un arrangement de quadriques dans R³. Nous définissons une décomposition "trapézoidale" dans le plan de balayage et étudions l'évolution de cette décomposition pendant le balayage. Une décomposition verticale de l'arrangement est calculée. L'exposé présentera les principaux problèmes de nature algébrique posés par cet algorithme.

Travail en commun avec B. Mourrain et JP Técourt (CGTA, 2005)

Retour à la liste des séminaires

Mardi 8 mars 2005, A006, 16h
Pierre-François Dutot, Imag, Grenoble.
Ordonnancement de tâches malléables sur plates-formes hiérarchique

Le modèle des tâches malléables est un modèle récent dans lequel les calculs sont regroupés dans des tâches pouvant utiliser plusieurs processeurs simultanément. La différence entre ce modèle et le modèle plus classique des tâches parallèles tient dans le fait que le nombre de processeurs affectés à chaque tâche n'est pas fixé par le programmeur qui écrit la tâche, mais par le gestionnaire de ressource. J'ai adapté ce modèle aux plates-formes hiérarchiques comme les grilles de multi-processeurs, et j'ai conçu des algorithmes d'ordonnancement garanti pour le cas des tâches sans contraintes de précédences (dans ma thèse) et plus récemment pour des tâches avec contraintes de précédences (travaux en cours).

Retour à la liste des séminaires

Vendredi 4 mars, B13, a 14h
Isabelle Sivignon, Laboratoire des Images et des Signaux (INPG), Grenoble
De la caractérisation des primitives à la reconstruction polyédrique de surfaces en géométrie discrète.

La géométrie discrète a pour objectif de définir dans l'espace discret, les objets, notions, propriétés géométriques du monde analogique, dans un souci de cohérence entre les deux mondes. Les problèmes faisant intervenir cette géométrie apparaissent en effet dès lors que l'on s'intéresse à l'analyse d'images discrètes (images numériques, médicales), pour la reconnaissance ou le codage de structures par exemple. Dans cet exposé, nous nous intéresserons à divers problèmes de géométrie discrète, de la caractérisation des objets géométriques de base comme les droites et les plans, jusqu'à la reconstruction polyédrique de surfaces discrètes. Cette évolution se décompose en deux grandes étapes, qui correspondent aux deux parties de cet exposé :

- une étude des objets de base de la géométrie discrète que sont les droites et les plans est proposée, en apportant notamment de nouveaux éléments de caractérisation de l'intersection de deux droites;

- nous voyons ensuite comment utiliser ces primitives pour la description d'objets discrets plus complexes, en présentant tout d'abord des résultats sur la segmentation d'une surface discrète en plans discrets, puis en proposant un algorithme de reconstruction polyédrique réversible d'une surface discrète à partir de cette segmentation.

Retour à la liste des séminaires

Jeudi 17 février, A006, a 16h
Gert Vegter, universite de Groningen (The Netherlands)
Computational aspects of homology theory.

This talk is a basic introduction to the computational aspects of homology theory. We review the notions of simplicial complex, Euler characteristic and Betti numbers for low dimensional complexes. Companion notes on Homology Theory, including some exercises, can be downloaded here.

Retour à la liste des séminaires

Mercredi 16 février, A006, a 11h
Gert Vegter, universite de Groningen (The Netherlands)
Certified meshing of implicit surfaces.

In this talk we present our recent work on certified meshing of implicit surfaces. These meshing algorithms generate piecewise linear approximations of an implicit surface that are homeomorphic, and even isotopic to this surface. This guaranteed (certified) topology is a distinctive feature of our methods, contrary to existing isosurface extraction algorithms, like the widely used marching cubes algorithm

Implicit surfaces are widely used to model geometric objects like molecules in biomolecular modeling, smooth surfaces reconstructed from MRI-data in image-guided surgery, or car parts in CAD/CAM-systems. The representation of a geometric object as an implicit surface, i.e., as an isosurface of a real-valued functions in three-space, may be very convenient for such physical or technical applications. However, for further geometry processing, like rendering the object on a computer screen or performing numerical simulations, it may be more convenient to have a piecewise linear (meshed) approximation of the object. Therefore, fast and reliable meshing algorithms have immediate applications in these practical situations.

All our algorithms compute a piecewise linear approximation of the implicit surface by using special subdivisions of three-space, adapted to the geometry of the object. Different meshing methods are obtained by chosing different subdivisions.

This is a survey of joint work with Jean-Daniel Boissonnat and David Cohen-Steiner (INRIA, Sophia Antipolis, France), Nico Kruithof and Simon Plantinga (Groningen University).

Retour à la liste des séminaires

Lundi 24 janvier, B11, 9h30 a 15h30
Séminaire ordonnancement.

9h30 -10h00 : Accueil

10h00 - 10h15 : Emmanuel Jeannot (Algorille): Introduction

10h15 - 11h00 : Anis Koubaa (TRIO) : Ordonnancement de messages dans les réseaux à commutation de paquets : vers l'intégration des contraintes (m,k)-firm dans les réseaux à débit garanti

11h00 -11h45 : Vandy Berten (Université Libre de Bruxelles) Distribution de jobs séquentiels dans le cas des grilles de calcul hétérogènes avec méta-scheduling (ou brokering) aléatoire.

13h30 - 14h15 : Julien Fondrevelle (Macsi) Approches de résolution pour les problèmes de flowshop avec contraintes d'attentes maximales et minimales entre opérations

14h15 - 15h00 : Frédéric Suter (Algorille) Ordonnancement de tâches parallèles en milieu hétérogène

15h00 -15h30: Discussions

Retour à la liste des séminaires

Jeudi 12 janvier, A208, 17h
Ernst Althaus, LORIA/MPII
Approximating Arbitrary Metrics by Tree Metrics.

2004

Lundi 29 novembre, B13, 11h
Kim Whittlesey, University of Illinois at Urbana Champaign
A solution to the braid group conjugacy problem that runs in quadratic time with very high probability.

In the early 2000s, group theorists looked into using braid conjugation as a one-way function for cryptography. However, a new algorithm to solve the conjugacy problem appears to run extremely quickly. We show that a simplification of this algorithm runs in quadratic time with very high probability. This is work in progress.

Retour à la liste des séminaires

Mercredi 17 novembre, B200, 9h
Martin Quinson, IMAG
Découverte de la topologie applicative d'une plate-forme de calcul

L'une des caractéristiques fondamentales des plates-formes de calcul distribué modernes est leur grande dynamicité, tant quantitative que qualitative. Il est donc indispensable de permettre aux applications de s'adapter à ces variations pour tirer le meilleur de ces architectures.

Si la surveillance des caractéristiques quantitatives de la grille (en terme de bande passante disponible, par exemple) est un problème relativement bien étudié dans la litérature, peu de travaux portent sur celui de l'optention des caractéristiques qualitatives telles que la topologie de niveau applicative.

La question est alors pour tout quadruplet de machines (abcd) donné de déterminer l'impact en terme de performances d'un transfert entre (ab) sur un tranfert entre (cd). De manière intuitive, si (ab) et (cd) partagent des ressources réseaux, ils vont également se partager la bande passante disponible. Il en découle par exemple qu'une communication de groupe ne devrait pas ordonnancer de transfert sur (ab) en meme temps que sur (cd).

Au cours de l'exposé, nous reviendrons sur ce que nous entendons par topologie *de niveau applicative*, et la grande différence avec la notion de topologie répandue dans la communauté réseau. Nous présenterons une modélisation mathématique qui nous permettera d'une part de formaliser le problème et d'autre part de proposer un algorithme permettant de résoudre ce problème dans la plupart des cas.

Retour à la liste des séminaires

Mardi 19 octobre, A208, 14h
Eric Colin de Verdiere, ENS Paris - CNRS
Shortening of curves and decomposition of surfaces

Some curves being drawn on a surface, we wish to shorten (or _optimize_) them as much as possible, while preserving some of their topological properties: the resulting curves should be obtained from the initial ones by a continuous transformation (homotopy or isotopy). This problem is thus a specialization of the problem of shortest path computation. It is relevant in geometric modelling and in computer graphics, notably for parameterizing surfaces.

More specifically, we wish to optimize two types of families of curves: a graph embedding (family of simple paths that can intersect only at common endpoints) or a family of simple, pairwise disjoint cycles. We restrict ourselves to a framework where all curves are drawn on the vertex-edge graph of a polyhedral surface.

We first consider families of curves that decompose topologically the surface, in the following sense: cutting the surface along the curves gives a disjoint union of topologically elementary surfaces (disks, cylinders, pairs of pants). We give greedy optimization processes for such families. We prove individual optimality of each curve of the resulting family. It is thus possible to optimize any family of curves by first extending it to a topological decomposition of the surface, and then by optimizing the latter family. The complexity of the resulting algorithms is polynomial in their input and in the ratio between the extremal weights of the edges of the vertex-edge graph.

This is partly joint work with Francis Lazarus.

Retour à la liste des séminaires

Mercredi 6 octobre, A008, 14h
Laurent Dupont, ISA
Paramétrage quasi-optimal de l'intersection de deux quadriques : théorie, algorithmes et implantations
Soutenance de thèse

Cette thèse présente un algorithme robuste et efficace du calcul d'une forme paramétrée exacte de la courbe d'intersection de deux quadriques définies par des équations implicites à coefficients rationnels. Pour la première fois, le paramétrage que nous obtenons contient toutes les informations topologiques de la courbe et est assez simple pour être exploité dans des applications géométriques non triviales.

De nombreux progrès, dans différents domaines, ont été nécessaires pour atteindre ce résultat. Nous avons réalisé une étude exhaustive de tous les cas possibles d'intersection, d'abord dans P³(C) en nous basant sur les travaux de Segre, puis dans P³(R) en exploitant les résultats d'Uhlig sur la réduction simultanée de deux formes quadratiques réelles. Cette étude systématique nous a permis de maîtriser complètement la géométrie inhérente à l'intersection de deux quadriques. Nous sommes maintenant capables de déterminer toutes les caractéristiques de la courbe d'intersection, à savoir son genre, ses points singuliers, le nombre de ses composantes algébriques et connexes, et les incidences entre ces composantes. Quand il en existe, nous trouvons un paramétrage rationnel des composantes de la courbe d'intersection. En ce sens, notre algorithme est optimal. Nous avons aussi fait des progrès significatifs sur la complexité de l'expression radicale des coefficients du paramétrage obtenu. Notre résultat est quasi-optimal dans le sens où les coefficients du paramétrage de la courbe d'intersection que nous calculons contiennent au plus une racine carrée non nécessaire dans leur expression. De plus, notre résultat est optimal dans le cas le pire, dans le sens où pour chaque type de courbe d'intersection (par exemple une quartique régulière, ou une cubique et une droite, ou deux coniques), il existe des paires de quadriques pour lesquelles le nombre de racines carrées apparaissant dans l'expression des coefficients de notre paramétrage est minimal.

Enfin, nous avons réalisé une implantation complète de notre algorithme en MuPAD qui nous a permis d'afficher des performances inédites, tant en terme de vitesse d'exécution qu'en terme de simplicité du résultat obtenu.

Retour à la liste des séminaires

Vendredi 1 octobre 2004, A006, 14h
Jeff Erickson, University of Illinois at Urbana-Champaign
Greedy optimal homotopy and homology generators

Many geometric problems, such as texture mapping, remeshing, and morphing, call for a topologically complex surface to be cut into one or more topological disks. Any orientable surface of genus g can be cut into a single topological disk by removing a so-called "system of loops" -- a set of 2g cycles sharing a common basepoint. I will describe a very simple greedy algorithm based on Dijkstra's shortest-path algorithm that computes the shortest system of loops with a given basepoint in O(n log n) time. This solves an open problem of Colin de Verdière and Lazarus. It is also possible to cut a surface into a single disk with a more general graph, but finding such a cut graph with minimum total length is NP-hard.

This is joint work with Kim Whittlesey, to appear at SODA 2005. Our paper is available at "http://www.cs.uiuc.edu/~jeffe/pubs/gohog.html".

Retour à la liste des séminaires

Mercredi 9 juin 2004, B011, 14h
Mathieu Giraud, , Symbiose, IRISA (Rennes)
Des architectures reconfigurables pour accélérer les calculs sur les bases de données génomiques

L'augmentation de la taille des bases de données génomiques est actuellement plus rapide que celle de la puissance de calcul des processeurs usuels. La conception de nouvelles architectures peut accélérer les traitements lourds sur ces bases de données.

L'équipe Symbiose de l'IRISA a ainsi développé une carte prototype, nommée R-disk, dans laquelle un processeur reconfigurable FPGA filtre des données en provenance d'un dispositif de stockage (un disque dur). Un réseau en étoile relie 48 cartes R-disk à un PC hôte qui envoie des requêtes et collecte les résultats.

La reconfigurabilité du FPGA permet d'envisager plusieurs applications tirant profit du parallélisme à grain fin d'architectures spécialisées. Nous présenterons principalement la recherche de motifs exprimés à l'aide d'automates pondérés et nous comparerons la solution R-disk aux solutions logicielles.

Nous évoquerons aussi l'utilisation d'heuristiques mettant en jeu des graines complexes dans la recherche de similitudes. Enfin, nous présenterons le projet ReMix, dans lequel le dispositif de stockage est désormais de la mémoire.

Retour à la liste des séminaires

Mardi 27 avril 2004, A008, 14h
Roman Kolpakov, Liverpool University
Real-time string matching in sublinear space

We study a problem of efficient utilisation of extra memory space in real-time string matching. We propose, for any constant $\varepsilon >0$, a real-time string matching algorithm claiming $O(m^{\varepsilon})$ extra space, where $m$ is the size of a pattern.

Retour à la liste des séminaires

Vendredi 16 avril 2004, B013, 14h
Fabien de Montgolfier, LIRMM Montpellier
Décomposition modulaire et intervalles communs

Considérons le problème de trouver les intervalles communs de plusieurs permutations. On s'intéresse à la consécutivité, et non à l'ordre. Par exemple, les permutations (abcde), (cdeba) et (edcab) ont comme intervalles communs {a,b,c,d,e}, {a,b}, {c,d,e}, {c,d} et {d,e}

Au cours de cette exposé, il sera montré le lien que ce problème entretient avec la décomposition modulaire, puisque les intervalles communs sont les modules de la relation d'ordre associée aux permutations. On verra qu'on peut coder le résultat, et le calculer, en temps O(n) au lieu du O(n2) naïf. Ce sera l'occasion de parler de la décomposition modulaire des graphes, et des algorithmes efficaces de calcul de celle-ci.

Retour à la liste des séminaires

Vendredi 5 mars 2004, B013, 11h
Franck Hetroy, Universitat Politècnica de Catalunya, Barcelone
Une méthode de détection d'étranglements sur une surface triangulée fermée

Un étranglement est une courbe (définie sur une surface fermée) simple, fermée, et de longueur localement (pour la distance de Hausdorff) minimale. Il correspond à une ``zone localement étroite'' sur la surface, comme le goulot d'une bouteille. Il est des surfaces naturelles comportant de nombreux étranglements : c'est notamment le cas dans l'industrie pétrolière des canaux chenalisants, qui sont un ensemble de poches de pétrole interconnectées. Il est parfois utile de détecter ces étranglements, afin de décomposer la surface en entités plus homogènes. Je propose ici une méthode de calculs d'étranglements sur une surface représentée sous forme de maillage triangulaire. Cette méthode procède en trois passes .Tout d'abord, elle simplifie progressivement la surface jusqu'à détection d'une configuration particulière appelée courbe germe. Elle calcule ensuite sur chaque surface intermédiaire, à partir de la courbe germe et jusqu'à la surface de départ, une géodésique par morceaux fermée. La géodésique par morceaux finale glisse ensuite le long de la surface vers la position d'un étranglement. Je montrerai et discuterai quelques résultats sur des surfaces diverses.

Retour à la liste des séminaires

Vendredi 5 mars 2004, B013, 11h
Jean Vuillemin, ENS Paris
Efficient Operations on Sparse Integers, Sets and Boolean Functions

We introduce a DAG structure for representing natural numbers. The binary representation of n = T(n0, p, n1) = n0+2^(2^p)*n1 is recursively split by trichotomy. Equal nodes are systematically shared. With respect to other operations, trichotomy presents no significant advantage over conventional arithmetics when dealing with dense numbers. The overhead can be made arbitrarily small by terminating the recursion at some depth, and by using conventional methods over leaf nodes.

Retour à la liste des séminaires

2003

Jeudi 11 décembre 2003, B011, 14h
Cédric Lamathe, Loria (Isa)
Une classification des 2-arbres exterplanaires selon leurs symétries

Ce séminaire a pour but d'introduire certains concepts de la théorie des espèces, fondée en 1981 par André Joyal, et de les illustrer en calculant explicitement la développement moléculaire de l'espèce des 2-arbres exterplanaires. Nous rappelons dans un premier temps les définitions de base de cette théorie, à savoir, les notions d'espèces, d'opérations combinatoires, d'espèces et de développement moléculaires, de séries associées,.... Nous illustrons alors ces concepts en proposant une classification explicite des 2-arbres exterplanaires par rapport à leurs symétries. Nous introduisons cette famille de structures arborescentes et en donnons quelques propriétés. Nous finissons en présentant la méthode générale utilisée basée sur un théorème de dissymétrie, des équations fonctionnelles et des formules d'addition combinatoires. Ce séminaire est issu de travaux réalisés avec Pierre Leroux et Gilbert Labelle.

Retour à la liste des séminaires

Vendredi 14 novembre 2003, B011, 14h
Mikhail A.Roytberg, Institute of Mathematical Problems in Biology, Russian Academy of Sciences, Pushchino, Moscow Region, Russia
From Analysis of Protein Structural Alignments Toward a Novel Approach to Align Protein Sequences

Alignment of protein sequences is a key step in most computational methods for prediction of protein function and homology-based modeling of three-dimensional (3D)-structure. We investigated correspondence between "gold standard" alignments of 3D protein structures and the sequence alignments produced by the Smith-Waterman algorithm, currently the most sensitive method for pair-wise alignment of sequences. The results of this analysis enabled development of a novel method to align a pair of protein sequences. The comparison of the Smith-Waterman and structure alignments focused on their inner structure and especially on the continuous ungapped alignment segments, "islands" between gaps. Approximately one third of the islands in the gold standard alignments have negative or low positive score, and their recognition is below the sensitivity limit of the Smith.Waterman algorithm. From the alignment accuracy perspective, the time spent by the algorithm while working in these unalignable regions is unnecessary. We considered features of the standard similarity scoring function responsible for this phenomenon and suggested an alternative hierarchical algorithm, which explicitly addresses high scoring regions. This algorithm is considerably faster than the Smith-Waterman algorithm, whereas resulting alignments are in average of the same quality with respect to the gold standard. This finding shows that the decrease of alignment accuracy is not necessarily a price for the computational efficiency.

Retour à la liste des séminaires

Jeudi 25 septembre 2003, A208, 14h
Celina Miraglia Herrera de Figueiredo, Federal University of Rio de Janeiro, Brazil
The homogeneous set sandwich problem

A homogeneous set is a non-trivial module of a graph, i.e. a non-unitary, proper subset H of a graph's vertices such that all vertices in H have the same neighbors outside H. Given two graphs G_1(V,E_1), G_2(V,E_2), the Homogeneous Set Sandwich Problem asks whether there exists a sandwich graph G_S(V,E_S), E_1 \subseteq E_S \subseteq E_2, which has a homogeneous set. Two years ago, Tang et al. proposed an interesting O(\triangle _1 ... n²) algorithm for this problem, which has been considered its most efficient algorithm since. We show the incorrectness of their algorithm and present a new deterministic algorithm for the Homogeneous Set Sandwich Problem, whose O(m_1 \overline{m_2}) time complexity becomes its current upper bound.

Joint work with Vinicius Gusmão, a PhD student at UFRJ.

Retour à la liste des séminaires

Vendredi 11 juillet 2003, B011, 14h
David Bremner, Univ. du Nouveau Brunswick, Canada
Separating and Classifying Hyperplanes in Minkowski Spaces

Whether two sets are seperable by hyperplanes is invariant under affine transformations, while distance is not. The near universal reduction of separation problems in practice to distance computations is on the surface thus a bit of a mystery. In this talk I will argue that the connection between distance and separation is necessary and natural as soon as one asks for the ``best'' separating hyperplane. On the other hand, it is often much more convenient to work with distance metrics different from the standard Euclidean one. It turns out that for polytopal metrics a strong duality relationship between distance and separation allows the straightforward computation of optimal separating hyperplanes by solving a primal-dual pair of linear programs. An especially interesting feature of this framework is that it works for input given explicitly as sets of points (where an LP solution is relatively well known, even for the Euclidean metric), but also for input given implicitly as intersections of halfspaces and Minkowski sums of line segments. I will round out the talk by discussing some possible approaches to the case when two sets are not separable by a hyperplane, and some connections with problems in pattern classification.

Joint work with Thomas Burger and Peter Gritzmann.

Retour à la liste des séminaires

Mardi 24 juin 2003, B013, 14h
Sue Whitesides, McGill university, Montréal
Rectangle Visibility Graphs: Characterization, Construction, and Compaction

Non-overlapping axis-aligned rectangles in the plane define visibility graphs in which vertices are associated with rectangles and edges are associated with visibility in either the horizontal or vertical direction. The recognition problem for such graphs is known to be NP-complete.

This talk introduces the notion of a topological rectangle visibility graph. This notion is designed to capture more precise visibility information from sets of axis-aligned rectangles than does the usual notion of a rectangle visibility graph. We give a combinatorial characterization of topological rectangle visibility graphs that are indeed realizable as sets of axis-aligned rectangles. Our characterization gives rise to a polynomial time algorithm for recognizing topological visibility graphs that are realizable, and in the case of realizable graphs, for constructing a realizing set of rectangles on the unit grid. The bounding box of these rectangles has optimum length in each dimension.

Our algorithm provides a rectangle compaction tool: given a set of rectangles, one computes the associated topological rectangle visibility graph, and then runs the algorithm to get an optimally compact set of rectangles with the same visibility properties.

Joint work with Ileana Streinu.

Retour à la liste des séminaires

Lundi 16 juin 2003, B013, 14h
Frank Sottile, university of Masssachusetts, Amherst
Common Transversals and Tangents

We describe some interesting symbolic computations that arose while studying the following simple geometric problem:

Consider k lines and 4-k spheres in R3.

1.When the given lines and spheres are general, how many lines are there that meet the fixed lines and are tangent to the spheres. Call these common tangents and transversals.

2.For which arrangements of lines and spheres are there infinitely many cmmon tangents and transversals?

Besides the interesting geometry, computation, and pictures, we feel that the study of geometry in 3-space is a fertile area for potential applications of symbolic and computational algebra. The results in this talk represent joint work with Gabor Megyesi and Thorsten Theobald.

See the web page featuring many, many pictures from this study.

Retour à la liste des séminaires

Jeudi 12 juin, A006, 14h
Ileana Streinu, Smith College, Massachusetts
Graph Realizations with partial Oriented Matroid constraints

From Mnev's celebrated universality theorem, it follows that realizing graphs with oriented matroid constraints is as hard as the existential theory of the reals. But if we only impose some partial oriented matroid constraints, how far can we go? We investigate this problem and some of its connections with rigidity theory. In particular, we show that every planar minimally rigid graph has a realization as a pseudo-triangulation.

Retour à la liste des séminaires

Mardi 10 juin, A006, 11h
Ludovic Meunier, INRIA Rocquencourt, projet Algo
Encyclopédie Automatique des Fonctions Spéciales

Le Handbook of Mathematical Functions [1] catalogue de nombreuses propriétés mathématiques et identités pour une centaine de fonctions dites spéciales. Toutes les formules de ce livre ont été calculées, écrites et vérifiées à la main.

The Encyclopedia of Special Functions (ESF) est une encyclopédie automatique sur les fonctions spéciales. Toutes les formules et les graphes de l'ESF ont été produits par des algorithmes.

Je consacrerai la première partie de mon exposé à la mise en place et à la description d'algorithmes utilisés dans l'ESF. J'introduirai en particulier le cadre mathématique de la D-finitude et l'adapterai pour aboutir à une structure de données pour représenter une fonction spéciale.

Dans un second temps, je présenterai l'ESF en tant que logiciel et décrirai la génération automatique du site web de l'ESF (http://algo.inria.fr/esf).

[1] Milton Abramowitz and Irene A. Stegun, editors. Handbook of mathematical functions with formulas, graphs, and mathematical tables. Dover Publications Inc., New York, 1992. Reprint of the 1972 edition.

Retour à la liste des séminaires

Vendredi 6 juin 2003, A006, 14h
Ciprian Borcea, Rider university
Singularities of Hinge Structures

Motivated by the hinge structure present in protein chains and other molecular conformations, we study the singularities of certain maps associated to structures with hinges.

(collaboration with I. Streinu, Smith college)

Retour à la liste des séminaires

Jeudi 22 mai 2003, A006, 14h
Yann Gerard, LLAIC1, IUT de Clermont-Ferrand
La programmation linéaire vue comme un problème de géométrie algorithmique

Dans un premier temps, nous nous intéresserons aux relations entre la polarité des cones polyhedriques et la programmation linéaire. Ce point de vue géométrique donne une interprétation naturelle et originale de la programmation linéaire comme un problème de géométrie algorithmique. Ce problème est connu sous le nom topmost convex combination on a line mais nous l'appelerons simplement optimisation sur une droite. Son énoncé est élémentaire:

Données: une partie finie P et une droite orientée D.

Question: trouver la face (ou l'une des faces) de l'enveloppe convexe de P par laquelle la droite orientée D "sort" de l'enveloppe convexe de P. Ce problème peut être posé de façon équivalente dans Rⁿ ou dans une sphère de Rⁿ. Nous verrons 3 algorithmes géométriques pour le résoudre. Les deux premiers sont des interprétations géométriques des algorithmes du simplex et de Megiddo tandis que le troisième est vraissemblablement un algorithme original.

Retour à la liste des séminaires

Lundi 12 mai 2003, A008, 15h
Sylvain Pion, MPII Saarbruecken
Calcul géométrique certifié

Les algorithmes geometriques sont tres sensibles aux problemes de robustesse numerique, specifiquement parce qu'ils combinent d'une part des aspects combinatoires lies a des manipulations de graphes, et d'autre part des aspects numeriques sensibles aux erreurs d'arrondis.

Une des approches pour resoudre ces problemes de maniere generale suit le paradigme du calcul geometrique exact. Nous allons presenter des methodes certifiees et efficaces pour le calcul geometrique exact, qui utilisent notamment des filtres arithmetiques, ainsi que les methodes exactes de manipulation de nombres algebriques utilisant des bornes de separation.

Retour à la liste des séminaires

Lundi 14 avril, au MPII Saarbrücken de 10h a 18h30
Lorraine-Saarland workshop on Geometry and CAD

Mercredi 19 mars 2003, B013 à 15h
Cyrille Damez, MPII Saarbruecken
Simulation globale de l''éclairage pour des séquences animées prenant en compte la cohérence temporelle

Les méthodes globales de simulation de l'éclairage permettent, à la différence des méthodes locales, d'exprimer l'équilibre énergétique dans les échanges entre différents objets, et donc de simuler précisément les effets subtils d'éclairage dûs aux nombreuses inter-réflexions. Il est donc naturel de souhaiter les utiliser pour la synthèse réaliste de films d'animation. Nous présenterons plus en détail au cours de cet exposé l'algorithme de radiosité hiérarchique spatiale et temporelle.

Plutôt que de résoudre une succession d'équations intégrales tri-dimensionelles, nous modélisons les échanges lumineux ayant lieu au cours de l'animation sous la forme d'une unique équation intégrale quadri-dimensionelle. Dans le cas ou l'intégralité des mouvements est connue à l'avance, nous proposons une extension de l'algorithme de radiosité hiérarchique mettant à profit la cohérence temporelle. La radiosité en chaque point et à chaque instant y est exprimée dans une base de fonctions hiérarchiques (multi-ondelettes) définies sur un maillage produit par un processus de raffinement. L'extension de ce maillage à un espace à quatre dimensions nous permet de calculer des échanges lumineux sur un intervalle de temps fini au lieu d'une date donnée. L'algorithme ainsi défini permet la simulation de l'éclairage global diffus dans une scène animée, dans un temps largement inférieur, avec une qualité équivalente à un calcul image par image.

Nous présenterons également des travaux plus récents permettant l'application de la méthode de tracé de chemin bidirectionel au cas des animations. Nous montrerons qu'un mécanisme de réutilisation des échantillons calculés permet de réduire le temps de calcul et d'éliminer les effets de scintillement dus à l'incohérence temporelle du bruit géneré par la méthode d'intégration.

Retour à la liste des séminaires

Lundi 10 mars, B013 à 15h30
Elmar Schoemer, Mainz University (Germany)
Collision detection and distance computation for quadratic complexes

The design-for-assembly technique requires realistic physically based simulation algorithms and in particular efficient geometric collision detection and distance computation routines. Mechanical parts in assemblies mostly consist of simply shaped surfaces, like planes, spheres, cylinders, cones and tori. Instead of approximating these parts by large polygonal models, we propose to work with the much smaller original CAD-data directly, thus avoiding precision and tolerance problems. We present generic algorithms, which can decide whether two solids intersect and which can compute the minimal Euclidean distance between them. We show how to computate the distance between two patches of quadratic surfaces trimmed by quadratic curves by solving univariate polynomials of a degree of at most 24. Moreover, we will identify an important subclass for which the degree of the polynomials is bounded by 8.

Retour à la liste des séminaires

2002

Mercredi 27 novembre
Susan Hert, MPII Saarbrücken
An Algorithm and Kernel for Exact Arrangements of Planar Conics

I will present some recent results from the EXACUS project (http://www.mpi-sb.mpg.de/EXACUS) related to the computation of arrangements of conics in the plane. We have developed an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that immediately leads to a realization of regularized boolean operations on conic polygons. I will discuss our representation of conics and how this leads to efficient and exact implementations of our kernel predicates using resultants and low-degree algebraic numbers. I will also discuss the sweep-line algorithm used for computing arrangements of planar curves with particular attention to the modifications required to accommodate non-linear curves.

Retour à la liste des séminaires

Jeudi 10 octobre
David Bremner, Univ. du Nouveau Brunswick, Univ. Techn. de Munich
Small Strictly Convex Quadrangulations of Point Sets

Discrete approximations of a surface or volume are necessary in numerous applications. Some examples are models of human organs in medical imaging, terrain models in GIS, or models of parts in a CAD/CAM system. These applications typically assume that the geometric domain under consideration is divided into small, simple pieces called finite elements. The collection of finite elements is referred to as a mesh. For several applications, quadrilateral/hexahedral mesh elements are preferred over triangles/tetrahedra.

In this paper, we give upper and lower bounds on the number of Steiner points (i.e. extra points) required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that $3 floor(n/2)$ internal Steiner points are always sufficient for a convex quadrangulation of $n$ points in the plane. Furthermore, for any given $n\geq 4$, there are point sets for which $ceil((n-3)/2)-1$ Steiner points are necessary for a convex quadrangulation.

Coauthor:
Ferran Hurtado (Univ. Politècnica de Catalunya, Barcelona, Spain)
Suneeta Ramaswami (Rutgers University, USA)
Vera Sacristàn (Univ. Politècnica de Catalunya, Barcelona, Spain)

Retour à la liste des séminaires

Jeudi 27 Juin
Journée QSL (Qualité et Sûreté du Logiciel) : Les outils de la vérification

Retour à la liste des séminaires

Jeudi 20 juin
Stephen Wismath, U. of Lethbridge, Dept. of Mathematics and Computer Science
Straight-Line Drawings on Restricted Grids in 2 and 3 Dimensions

We consider straight-line crossing-free drawings of classes of graphs where vertices are mapped to integer-valued coordinates. We show that all outerplanar graphs can be drawn in $O(n)$ volume in 3 dimensions on a universal grid and investigate the graphs drawable on 2 special restricted grids called the prism and the box. We also characterize the trees drawable (in 2 dimensions) on an $n$ x $k$ grid.

Joint work with Stefan Felsner (Freie Universitaet, Berlin) and Beppe Liotta (U. Perugia, Italy).

Retour à la liste des séminaires

Mercedi 12 juin
Siu-Wing Cheng, Hong-Kong (HKUST)
Hierarchy of Surface Models and Irreducible Triangulation

Given a triangulated closed surface, the problem of constructing a hierarchy of surface models of decreasing level of detail has attracted much attention in computer graphics. A hierarchy provides view-dependent refinement and facilitates the computation of parameterization. For a triangulated closed surface of $n$ vertices and genus $g$, we prove that there is a constant $c > 0$ such that if $n > c\cdot g$, a greedy strategy can identify $\Theta(n)$ topology-preserving edge contractions that do not interfere with each other. Further, each of them affects only a constant number of triangles. Repeatedly identifying and contracting such edges produces a topology-preserving hierarchy of $O(n + g^2)$ size and $O(\log n + g)$ depth. In practice, the genus $g$ is very small when compared with $n$ for large models and the selection of edges can be enhanced by measuring the error of their contractions using some known heuristics. Although several implementations exist for constructing hierarchies, our work is the first to show that a greedy algorithm can efficiently compute a hierarchy of provably small size and low depth. When no contractible edge exists, the triangulation is irreducible. Nakamoto and Ota showed that any irreducible triangulation of an orientable 2-manifold has at most max{342g-72,4} vertices. Using our proof techniques we obtain a new bound of max{240g,4}.

Retour à la liste des séminaires

Mardi 28 mai
Pierre Alliez, INRIA Sophia-Antipolis, Prisme
Parameterization and Interactive Remeshing of Surface Meshes

As 3D geometry becomes a prevalent media, a proliferation of meshes are readily available, coming from a variety of sources including 3D scanners, modeling software, and output from computer vision algorithms. Although these meshes capture geometry accurately, their sampling quality is usually far from ideal for subsequent applications (e.g., editing, geometry processing, storage, transmission).

In this talk, I will present a novel technique, both flexible and efficient, for interactive remeshing of irregular geometry. First, the original (arbitrary genus) mesh is substituted by a series of 2D maps in parameter space. Using these maps, our algorithm is then able to take advantage of established signal processing and halftoning tools that offer real-time interaction and intricate control. The user can easily combine these maps to create a control map, a map which controls the sampling density over the surface patch. This map is then sampled at interactive rates allowing the user to easily design a tailored resampling. As a result, our remeshing technique is extremely versatile and general, being able to produce arbitrarily complex meshes with a variety of properties including: uniformity, regularity, semi-regularity, curvature sensitive resampling, and feature preservation.

Time permitting, I will get to the "future work" part of the talk, and describe two directions of research. The first one consists of interleaving boundary and topology filtering with surface resampling in a unified framework. The second direction - more challenging - makes it possible to switch from point sampling to edge sampling, and obtain this way a direct anisotropic polygon remeshing engine.

Retour à la liste des séminaires

Lundi 27 mai
Kurt Mehlhorn, MPII Saarbrücken
EXACUS: Efficient and Exact Computations with Curves and Surfaces

The aim of the project is to develop a system for exact and efficient geometric computing with curves and surfaces and its theoretical underpinning. After a short discussion of the goals, I discuss first results: a geometry kernel for conic sections, algorithms for algebraic numbers of small degree, and boolean operations on conic polygons.

A ``conic polygon'' is any set that can be obtained from conic half-spaces (= the set of points in the plane in which a linear or quadratic function is positive) by regularized boolean operations.

Our algorithms and their implementations are complete (they can deal with all inputs), exact (they deliver the mathematical correct result) and efficient (they can handle inputs with thousands of primitives).

The project uses results from computational geometry, solid modeling, computer algebra, and numerical analysis.

Retour à la liste des séminaires

Lundi 27 mai
Juha Kärkkäinen, MPII Saarbrücken
Better filtering with gapped Q-grams

A popular and much studied class of filters for approximate string matching compares substrings of length q, the q-grams, in the pattern and the text to identify text areas that contain potential matches. A generalization of the method that uses _gapped_ q-grams instead of contiguous substrings is mentioned a few times in literature but has never been analyzed in depth. We show both theoretically and experimentally that gapped q-grams can provide orders of magnitude faster and/or more efficient filtering than contiguous q-grams. To achieve these results the arrangement of the gaps in the q-grams and a filter parameter called a threshold have to be optimized. Both of these tasks are nontrivial combinatorial optimization problems for which we have developed efficient solutions.

Retour à la liste des séminaires

Mardi 21 mai
Antoine Vigneron, Hong Kong University of Science and Technology
Motorcycle Graphs and Straight Skeletons

The straight skeleton of a polygon represents the edges of a roof whose faces have same slope, and that has exactly one face per edge of the input polygon. Its most direct application is to compute offset lines in Computer Aided Design. It has also been used for surface reconstruction from cross-sections in medical applications. More generally, it can be seen as a replacement for the medial axis with straight line edges.

We give a reduction from the problem of computing the straight skeleton of a simple polygon to the so-called motorcycle graph problem. We give an improved algorithm for computing motorcycle graphs. Combining these results, we obtain an efficient randomized algorithm for computing the straight skeleton of a simple polygon. It is simpler, and faster in expectation, than the previous best known algorithm.