En analyse de tolérances géométriques, une approche consiste à manipuler des polyèdres de R' issus d’ensembles de contraintes linéaires. La position relative entre deux surfaces quelconques d'un mécanisme est déterminée par des opérations (somme de Minkowski et intersection) sur ces polyèdres. Ces polyèdres ne sont pas bornés selon les déplacements illimités dus aux degrés d’invariance des surfaces et aux degrés de liberté des liaisons.Dans une première partie sont introduits des demi-espaces "bouchons" destinés à limiter ces déplacements afin de transformer les polyèdres en polytopes. Cette méthode implique de maîtriser l’influence des demi-espaces bouchons sur la topologie des polytopes résultants. Ceci est primordial pour garantir la traçabilité de ces demi-espaces dans le processus d’analyse de tolérances.Une seconde partie dresse un inventaire des problématiques de mise en oeuvre numérique des polytopes. L’une d’entre elles repose sur le choix d’une configuration de calcul (point et base d’expression, coefficients d’homogénéisation) pour définir un polytope. Après avoir montré que le changement de configuration de calcul est une transformation affine, plusieurs stratégies de simulations sont déclinées afin d’appréhender les problèmes de précision numérique et de temps de calculs. / In geometric tolerancing analysis area, a classical approach consists in handling polyhedrons coming from sets of linear constraints. The relative position between any two surfaces of a mechanism is determined by operations (Minkowski sum and intersection) on these polyhedrons. The polyhedrons are generally unbounded due to the inclusion of degrees of invariance for surfaces and degrees of freedom for joints defining theoretically unlimited displacements.In a first part are introduced the cap half-spaces to limit these displacements in order to transform the polyhedron into polytopes. This method requires controlling the influence of these additional half-spaces on the topology of calculated polytopes. This is necessary to ensure the traceability of these half-spaces through the tolerancing analysis process.A second part provides an inventory of the issues related to the numerical implementation of polytopes. One of them depends on the choice of a computation configuration (expression point and base, homogenization coefficients) to define a polytope. After proving that the modification of a computation configuration is an affine transformation, several simulation strategies are listed in order to understand the problems of numerical precision and computation time.

La propagation acoustique en milieu externe est fortement influencée par l'environnement. Les effets liés à la géométrie, comme la topographie ou la présence d'obstacles, sont principalement les réflexions et les diffractions. Concernant l'effet de l'atmosphère, les gradients moyens génèrent des réfractions tandis que la turbulence provoque des fluctuations aléatoires et une perte de cohérence du signal. La plupart de ces effets sont généralement bien décrits de manière théorique, cependant dans les configurations réelles le cumul de tous ces effets rend l'utilisation des expressions analytiques très difficile. Les études expérimentales présentent également des limites liées à la difficulté de connaître l'environnement parfaitement et d'isoler un effet physique particulier. Dans cette perspective, la simulation numérique est une alternative pratique et complémentaire à la théorie et l'expérimentation. Parmi les modèles numériques de propagation existants, ceux basés sur une résolution par différences finies dans le domaine temporel (FDTD pour Finite-Difference Time-Domain) des équations d'Euler linéarisées sont récents et particulièrement prometteurs. Cependant comme pour tout modèle nouveau, il reste à montrer qu'effectivement l'ensemble des phénomènes physiques d'intérêt sont retranscrits.Dans le cadre de ses études sur la propagation acoustique extérieure, l’Institut franco-allemand de recherches de Saint-Louis (ISL) a implémenté un tel modèle de propagation. Cette implémentation est ci-après appelée ITM, pour ISL FDTD Model. L'objectif de cette thèse, proposée par l'ISL en collaboration avec le Laboratoire de Mécanique des Fluides et d'Acoustique (LMFA), est de poursuivre le développement et les validations de cette implémentation. Une part importante du travail consiste également à illustrer les potentialités du code ITM pour des applications de propagation de signaux acoustiques complexes dans un environnement complexe. [...] / Outdoor sound propagation is strongly influenced by the environment. The geometry, such as topography and the presence of obstacles, alters the sound through reflexions and diffractions. Regarding atmosphere-related effects, the mean gradients produce refractions while turbulence cause random fluctuations and signal coherence loss. Most of those effects are generally well described theoretically. Still, in real configurations, the accumulation of those effects makes the use of analytical expressions difficult. Experimental studies are also limited because of difficulties in perfectly determining the environment or in separating a precise physical effect. In that perspective, numerical simulation is a convenient and complementary alternative approach to theory and experimentation. Among the existing numerical propagation models, those based on a Finite-Difference resolution in the Time-Domain (FDTD) of the linearized Euler equations are recent and particularly promising. However as for every new model, it remains to show that indeed the physical phenomena of interest are reproduced. In the framework of its studies on outdoor sound propagation, the french-german research Institute of Saint-Louis (ISL) has implemented such a propagation model. This implementation is hereafter called ITM, for ISL FDTD Model. The objectives of the thesis, proposed by ISL in collaboration with the Laboratory of Fluid Mechanics and Acoustics (LMFA), are to pursue the developments and validations of this implementation. An important part of the work is also given on the illustration of the potentialitiesof the ITM code in propagating complex acoustic signals in complex environments. […]

L'analyse de la déformation des massifs subalpins de Vercors et Chartreuse, qui constituent l'avant-pays des massifs cristallins externes de Belledonne et du Pelvoux chevauchant vers l'Ouest, a permis de reconstituer le champ de déplacement ainsi que l'état initial avant déformation de cet avant-pays. Cette analyse repose sur un grand nombre de données géologiques et géophysiques, et en particulier sur des données issues de profils sismiques réalisés dans les massifs subalpins. Ces données ont permis de préciser la géométrie des structures profondes, et notamment la position des plans de décollement. Deux méthodes. qui intègrent toutes les données disponibles dans un schéma de déformation cohérent. ont été utilisées. Il s'agit d'une part de la construction de coupes géologiques équilibrées et d'autre part de l'établissement de carte de déformation finie. La déformation globale des massifs subalpins de Vercors et de Chartreuse est liée principalement au chevauchement crustal de la partie externe du massif de Belledonne et peut se décomposer en deux étapes majeures : un premier chevauchement de grande ampleur déformé ensuite par des épisodes chevauchants secondaires.

Les travaux présentés dans cette thèse s'inscrivent dans la cadre de la planification de trajectoires optimales en présence d'obstacles pour des robots mobiles de type voiture et pour des robots à pattes. Le modèle de robot de type voiture étudié est celui de Dubins. Il s'agit grossièrement d'une voiture se déplaçant en marche avant uniquement et dont le rayon de braquage est minoré par 1. Nous avons considéré le problème du calcul d'une enveloppe convexe de courbure bornée d'un ensemble S de points du plan, c'est-à-dire d'un ensemble contenant S et dont le bord est de courbure bornée et de périmètre minimal. Nous montrons que si le rayon du plus petit disque contenant S est supérieur à 1, une telle enveloppe est unique. Nous montrons que le calcul d'une enveloppe convexe de courbure bornée se ramène à un problème d'optimisation convexe ou à la résolution d'un ensemble de systèmes algébriques. Nous proposons également un algorithme exact polynomial pour le calcul de trajectoires optimales en longueur lorsque le robot se déplace en présence d'obstacles dont les bords sont de courbure bornée et constitués de segments de droite et d'arcs de cercle. De tels obstacles peuvent être obtenu comme enveloppes convexes de courbure bornée d'obstacles polygonaux. L'algorithme calcule un graphe et recherche un plus court chemin dans ce graphe. Le calcul de ce graphe est effectué grâce à des techniques de géométrie algorithmique et par la résolution de systèmes algébriques dont nous montrons, à l'aide de résultants, qu'ils ont un nombre fini de solutions. Nous avons également étudié le problème de la planification de trajectoires pour des robots à pattes dont le corps est ponctuel et dont toutes les pattes sont attachées au même point. Les pattes du robot ont une longueur bornée et ne sont autorisées à se poser que dans certaines régions polygonales du plan. Nous présentons un algorithme quasi optimal pour le calcul de l'ensemble des positions du corps du robot en équilibre stable. Par une transformation judicieuse, nous nous ramenons au calcul de l'espace libre d'un robot de la forme d'un demi disque se déplaçant en présence d'obstacles.

Cette thèse d'habilitation présente une synthèse de contributions dans le domaine du traitement numérique de la géométrie sous la forme de concepts et d'algorithmes pour la reconstruction de surfaces, l'approximation de surfaces, le remaillage quadrangle de surfaces et la génération de maillages.

Les travaux présentés dans ce mémoire d'habilitation correspondent à des recherches effectuées depuis mon arrivée à Bordeaux en septembre 1999. J'ai choisi d'y présenter celles qui ont trait aux approches non-euclidiennes pour l'analyse d'image, la clé de voûte en étant la segmentation par modèle déformable. D'autres travaux plus amonts comme la topologie des espaces subdivisés et les invariants topologiques ou plus avals comme la reconstruction de colonne vertébrale en imagerie radiographique ne seront qu'évoqués. Ce choix, s'il peut sembler restrictif par rapport à une synthèse exhaustive de mes travaux, présente néanmoins une plus grande cohérence, à la fois dans les résultats et dans la démarche suivie. Ce mémoire montre notamment que l'utilisation d'autres géométries que la géométrie euclidienne classique, les géométries riemannienne et discrète, présente un intérêt certain en analyse d'images. Les modèles déformables constituent une technique classique de segmentation et de reconstruction en analyse d'image. Dans ce cadre, le problème de la segmentation est exprimé sous forme variationnelle, où la solution est idéalement le minimum d'une fonctionnelle. Pendant ma thèse, je m'étais déjà intéressé aux modèles hautement déformables, qui ont la double caractéristique de se baser uniquement sur l'information image pour repérer ses composantes et de pouvoir extraire des formes de complexité arbitraire. Pour assurer l'initialisation du modèle déformable, j'avais aussi mis en évidence les liens entre surfaces discrètes et triangulations d'isosurfaces. Ces premiers travaux expliquent le cheminement que j'ai suivi depuis dans mes recherches. En voulant attaquer deux problématiques fondamentales des modèles déformables (la minimisation du nombre de paramètres et de la complexité, la recherche d'une solution plus proche de l'optimale), j'ai été amené à changer l'espace de travail classique : l'espace euclidien. Le Chapitre 1 résume les approches classiques des modèles déformables, leurs différentes formulations, ainsi que les problématiques spécifiques auxquelles je me suis intéressé. Il montre enfin en quoi la formulation des modèles déformables dans des espaces non-euclidiens ouvre des pistes intéressantes pour les résoudre. La première voie explorée et résumée dans le Chapitre 2 est d'introduire une métrique riemannienne, variable dans l'espace et dépendante de l'information image locale. L'utilisation d'une autre métrique permet de déformer virtuellement l'espace afin de concentrer l'effort de calcul sur les zones d'intérêt de l'image. Une métrique judicieusement choisie permet d'adapter le nombre de paramètres du modèle déformable à la géométrie de la forme recherchée. Le modèle pourra ainsi se déplacer très vite sur les zones homogènes, extraire les parties droites, planes ou peu courbées avec très peu de paramètres, et conserver une grande précision sur les contours significatifs très courbés. Une telle approche conserve voire améliore la qualité et la robustesse de la segmentation, et minimise à la fois la complexité en temps et le nombre d'itérations avant convergence. La deuxième voie explorée parallèlement est le remplacement de l'espace euclidien continu par la grille cellulaire discrète. L'espace des formes possibles est alors fini tout en restant adapté à l'échantillonnage de l'image. D'autres techniques d'optimisation sont dès lors envisageables, la solution est bien définie et les problèmes numériques liés à la convergence d'un processus ne sont plus présents. Le Chapitre 3 décrit le principe suivi pour discrétiser le modèle déformable sur la grille cellulaire Z^n. Il présente les premiers résultats obtenus avec un algorithme de segmentation a posteriori. Il met aussi en évidence les problématiques soulevées par le passage au discret, problématiques qui se sont révélées être des voies de recherche par elles-mêmes. D'une part, il faut mettre au point des structures de données et des outils pour représenter les surfaces discrètes, pour mesurer leurs paramètres géométriques, et pour les faire évoluer. Le Chapitre 4 synthétise les travaux menés en ce sens. Cela nous conduit à proposer un nouveau formalisme algébrique pour représenter ces surfaces en dimension quelconque. Une étude précise des estimateurs géométriques discrets de tangente, de normale, de longueur et de courbure est ensuite conduite. Nous avons notamment évalué quantitativement leurs performances à basse échelle et proposé de nouveaux estimateurs pour les améliorer. Leurs propriétés asymptotiques lorsque la discrétisation est de plus en plus fine sont enfin discutées. D'autre part, le modèle déformable discret doit approcher au mieux le comportement du modèle déformable euclidien à résolution donnée mais aussi simuler de plus en plus exactement ce comportement lorsque la résolution augmente asymptotiquement. Les estimateurs géométriques discrets se doivent dès lors d'être convergents. En analysant finement la décomposition des courbes discrètes en segments discrets maximaux, nous avons obtenu des théorèmes de convergence ou de non-convergence de certains estimateurs. Le Chapitre 5 résume cette étude de la géométrie des courbes discrètes 2D et des propriétés géométriques asymptotiques du bord d'une discrétisation. Le mémoire se conclut par une synthèse des principaux résultats obtenus et montre les perspectives de recherche ouvertes par ces travaux.

La Géométrie de l'Interaction (GdI) de Girard est une sémantique des langage de programmations tenant compte de leur dynamique de réduction.<br />Dans un premier temps, on présente les réseaux d'interaction de Lafont comme une instance particulière de GdI. Puis, on définis un cadre général d'étude de la GdI à partir d'un ensemble de symboles et de règles d'interaction.<br />Dans un second temps, on introduit une notion de concision associée à la GdI et on montre dans quelle mesure cette notion fait du sens à l'aide d'une famille d'exemple basée sur les entiers de Church.<br />Dans un dernier temps, on présente les réseaux d'interaction différentiels d'Ehrhard et Regnier et on définit leur GdI. On montre que la théorie usuelle de Danos-Regnier est entièrement récupérée.

Étant donné un ensemble S de points du plan, une triangulation de S est une décomposition de l'enveloppe convexe de S en triangles dont les sommets sont les points de S. Une triangulation de S est dite de Delaunay si le cercle circonscrit à chaque triangle ne contient aucun point de S en son intérieur. Dans cette thèse, nous étudions une généralisation de ces notions à un ensemble S de segments disjoints du plan.<br />Nous commençons par définir une nouvelle famille de diagrammes, appelés triangulations de segments. Nous étudions leurs propriétés géométriques et topologiques et nous donnons un algorithme pour construire efficacement une telle triangulation.<br />Nous généralisons ensuite la notion de triangulation de Delaunay aux triangulations de segments et nous mettons en évidence la dualité avec le diagramme de Voronoï de segments.<br />Nous étendons également la légalité des arêtes au cas des triangulations de segments en définissant, d'une part, la légalité géométrique qui caractérise la triangulation de Delaunay de segments parmi l'ensemble de toutes les triangulations de segments possibles et, d'autre part, la légalité topologique qui caractérise les triangulations de segments qui ont la même topologie que celle de Delaunay.<br />Enfin, nous décrivons un algorithme de « flip » qui transforme toute triangulation de segments en une triangulation qui a la même topologie que celle de Delaunay. À l'aide de fonctions localement convexes, nous démontrons que la suite de triangulations construites par cet algorithme converge vers celle de Delaunay et nous prouvons qu'une triangulation de segments qui a la même topologie que celle de Delaunay est obtenue après un nombre fini d'étapes.

Ce travail est une étude algorithmique et mathématique préparant une axiomatisation ou une spécification de la géométrie dynamique. Le comportement dynamique des intersections de courbes, dans le cas où elles sont multiples, et la gestion algorithmique d'objets géométriques sous-déterminés posent problème. Il est connu depuis peu que la continuité des déplacements et le déterminisme des comportements dynamiques ne sont pas entièrement compatibles ; ce travail précise ce point essentiel : par des procédés globaux qui sortent du cadre de la géométrie discrète, il est montré que le comportement dynamique des intersections de cercles présente des singularités inévitables, qui sont énumérées. Une tentative est faite pour étendre ce résultat aux intersections de coniques. Des propositions pour unifier le traitement algorithmique d'objets sous-déterminés, comme les points sur objet, sont présentées, depuis le cadre mathématique jusqu'à l'implémentation effective. Ce travail montre aussi qu'il existe des concepts mathématiques de base, comme la notion d'aire non signée, dont la justification ultime ne supporte pas le mouvement, au contraire de la notion d'aire signée. En permettant la spécification des algorithmes traitant du comportement dynamique des intersections de cercles, ce travail établit un premier niveau de qualité pour les logiciels de géométrie dynamique, permettant de juger leur cohérence mathématique. Plusieurs des implémentations réalisées sont présentes dans Cabri2 Plus, logiciel largement diffusé par l'entreprise Cabrilog. Au niveau théorique, ce travail repose différemment la question de la nature des figures dynamiques, en particulier de la nature mathématique précise des lieux géométriques en géométrie dynamique.

Le but de cette thèse est de catégorifier des algèbres amassées antisymétrisables. Unegrande variété de cas antisymétriques a déjà été traitée par exemple par Keller, Caldero-Keller, Geiß-Leclerc-Schröer, Dehy-Keller, Fu-Keller, Palu. Pour ce faire, on utilise descatégories exactes stablement 2-Calabi-Yau. Pour traiter le cas antisymétrisable, nous considérons l'action d'un groupe fini sur une telle catégorie et nous introduisons unecatégorie équivariante associée qui est encore stablement 2-Calabi-Yau. Nous dévelop-pons une théorie des mutations pour ses objets rigides invariants. Une grande famille d'exemples est fournie par les catégories de représentations d'algèbres préprojectives : par exemple, si l'on prend la catégorie des représentations de l'algèbre préprojective de diagramme A(2n-1) muni de son automorphisme d'ordre 2, on obtient l'algèbre amassée des fonctions sur le groupe de Lie unipotent de type C(n). On peut de la même façon obtenir toutes les algèbres amassées de fonctions sur les sous-groupes unipotents maximaux des groupes de Lie semi-simple. Par ailleurs, on peut construire ainsi toutes les algèbres amassées de type fini. Toutes ces catégorifications nous permettent de démontrer, pour les algèbres amassées correspondantes, une conjecture de Fomin et Zelevinsky qui affirme l'indépendance linéaire des monômes d'amas.