Search

This thesis aims at evaluating the size of the Delaunay triangulation of points drawn on a surface with a random distribution. The Delaunay triangulation, is a geometrical object that appeared recurrently in the scientific history. In dimension 2, the Delaunay triangulation is the set of triangles for which the circumscribing circle does not contain other points of X. This definition is generalizable in higher dimensions.Today, the Delaunay triangulation is one the most studied structures in computational geometry. For the 2 dimensional case, we know that the size of the Delaunay triangulation remains linear with the number of points. In 3 dimension, it is not anymore the case. The size of the 3D-Delaunay triangulation can range from linear to quadratic. This size depends on how the points are distributed in R^3. On a surface, the size of the Delaunay triangulation will depend both on the surface and on how they are distributed on this surface.To model points, we choose to use a Poisson point process since it verifies properties of homogeneity and independence that are convenient for the computations. In order to prove the expected O(n log n) bound for the uniform sample distributed on a cylinder, Devillers et al. remarked that the intersection of the cylinder with a sphere passing though two points p and q on the cylinder always contains a specific triangle drawn on the cylinder. That leads them to study a 2-dimensional graph in which two points are neighbors if there exists such a triangle that does not contain other data points. Such a graph has expected size O(n log n), and this is how they obtain the O(n log n) bound. In Part II, we define a kind of empty region graphs, we formalize a method to compute lower and upper bounds on their expected size, and give tight results for such graphs.As Attali et al. pointed out, the intersection of a sphere with a generic surface has almost an elliptic shape, aligned with the curvature directions of the surface. This leads us to study a particular empty region graph for which the regions are axis-aligned ellipses. We prove, in Part II, that if theinvolved ellipses have an aspect ratio ranging from b to 1, with 0 < b < 1, then the expected number of neighbors of any point in the graph is O(ln b).In order to illustrate the method, we compute, in Part III, tight asymptotic bounds on the expected size of the 3D-Delaunay triangulation in two specific cases. In Part III, Chapter 12, we consider a cylinder of revolution and reprove the O(N ln N) bound but for a Poisson point process. Considering the similarity between uniform and Poisson sample, the goal of this chapteris mainly to present concretely the method in a 3-dimensional simple case. Then, in Chapter 13, we compute the size of the 3D-Delaunay triangulation of a Poisson process distributed on a flattened sphere. We show that the expected size of the triangulation is O(N).Finally in Part IV, we treat the case of generic surfaces. Even if an oblate spheroid is a specific surface, we will be able to reuse some computations in this part up to some adaptations. Indeed the oblate spheroid is the surface of a convex body, that is not generally the case. It has a lot of symmetries,that is not generally the case either. In this part, we focus more on how to deal with these adaptations than on the computations that were already quite tedious in the spheroid case., Cette thèse a pour but d' évaluer la taille de la triangulation de Delaunay de points distribués sur une surface avec une distribution aléatoire. La triangulation de Delaunay, est un objet géométrique qui est apparu de manière récurrente dans l'histoire scientifique. En dimension 2, la triangulation de Delaunay de X est l'ensemble des triangles pour lesquels le cercle circonscrit ne contient pas d'autres points de X. Cette définition est généralisable en dimension supérieure.Aujourd'hui, la triangulation de Delaunay est l'une des structures les plus étudiées en géométrie algorithmique. Pour le cas en 2 dimensions, on sait que la taille de la triangulation de Delaunay reste linéaire avec le nombre de points. En 3 dimensions, la taille de la triangulation de Delaunay peut varier de linéaire à quadratique. Cette taille dépend de la façon dont les points sont distribués dans R^3. Sur une surface, la taille de la triangulation de Delaunay dépendra à la fois de la surface et de la façon dont ils sont répartis sur cette surface.Pour modéliser les points, nous choisissons d'utiliser un processus ponctuel de Poisson car il vérifie des propriétés d'homogénéité et d'indépendance qui sont pratiques pour les calculs. Afin de prouver la borne O(n log n) en espérance pour l'échantillon uniforme distribué sur un cylindre, Devillers et al. ont remarqué que l'intersection du cylindre avec une sphère passant par deux points p et q sur le cylindre contient toujours un triangle spécifique dessiné sur le cylindre. Cela les conduit à étudier un graphe à 2 dimensions dans lequel deux points sont voisins s'il existe un tel triangle qui ne contient pas d'autres points de données. Un tel graphe a une taille moyenne de O(n log n), et c'est ainsi qu'ils obtiennent la borne O(n log n). Dans la partie II, nous définissons un type de graphes de régions vides, nous formalisons une méthode pour calculer les limites inférieures et supérieures de leur taille moyenne, et nous donnons des résultats optimaux pour ces graphes.Comme Attali et al. l'ont souligné, l'intersection d'une sphère avec une surface générique a presque une forme elliptique, alignée avec les directions de courbure de la surface. Ceci nous amène à étudier un graphe particulier de régions vides pour lequel les régions sont des ellipses alignées avec les axes. Nous prouvons, dans la partie II, que si les ellipses concernées ont un rapport d'aspect compris entre b et 1, avec 0 < b < 1, alors le nombre moyen de voisins de tout point du graphe est O(ln b).Afin d'illustrer la méthode, nous calculons, dans la partie III, les limites asymptotiques sur la taille moyenne de la triangulation 3D-Delaunay dans deux cas spécifiques. Dans la partie III, chapitre 12, nous considérons un cylindre de révolution et confirmons la limite O(n ln n) mais pour un processus ponctuel de Poisson. Compte tenu de la similitude entre l'échantillon uniforme et l'échantillon de Poisson, le but de ce chapitreest principalement de présenter concrètement la méthode dans un cas simple en 3 dimensions. Ensuite, dans le chapitre 13, nous calculons la taille de la triangulation 3D-Delaunay d'un processus de Poisson distribué sur une sphère aplatie. Nous montrons que la taille moyenne de la triangulation est O(n).Enfin, dans la partie IV, nous traitons le cas des surfaces génériques. Même si un sphéroïde aplati est une surface spécifique, nous pourrons réutiliser certains calculs de cette partie moyennant quelques adaptations. En effet, le sphéroïde aplati est la surface d'un corps convexe, ce qui n'est généralement pas le cas en général. Dans cette partie, nous nous concentrons plus sur la façon de gérer ces adaptations que sur les calculs qui étaient déjà assez fastidieux dans le cas du sphéroïde.

A set $S \subset \mathbb{Z}^d$ is \emph{digital convex} if $\conv(S) \cap \mathbb{Z}^d = S$, where $\conv(S)$ denotes the convex hull of $S$.Herein, we consider various algorithmic problems related to recognizing digital convex sets or finding digital convex subsets.We show that the quickhull algorithm runs in linear time for digital convex sets and use this result to provide an algorithm for testing the digital convexity of $S\subset \mathbb{Z} ^2$ in $O(n + h \log r)$ time, where $h$ is the number of edges of the convex hull and $r$ is the diameter of $S$. We then extend this result and show how this can be used to solve the digital convex set recognition problem in the same time complexity.Finally, we provide polynomial time algorithms to find the largest union of $k$ digital convex subsets of $S\subset \mathbb{Z} ^2$.; Un ensemble $S \subset \mathbb{Z}^d$ est \emph{convexe discret} si $\conv(S) \cap \mathbb{Z}^d = S$, où $\conv(S)$ est l'enveloppe convexe de $S$.Ici, nous considérons plusieurs problèmes algorithmiques traitant de la reconnaissance d'ensembles convexes discrets ainsi que de la détection de sous ensembles convexes discrets.Nous montrons que l'algorithme quickhull s'exécute en temps linéaire pour des ensembles convexe discret. Puis nous utilisons ce résultat afin de proposer un algorithme qui teste la convexité discrète de $S\subset \mathbb{Z} ^2$ en $O(n + h \log r)$ temps, où $h$ est le nombre de sommet de l'enveloppe convexe de $S$ et $r$ est le diamètre de $S$. Ensuite, nous étendons ce résultat et montrons comment il peut être utilisé afin de résoudre le problème de reconnaissance d'ensemble convexe discret. Enfin, nous proposons un algorithme en temps polynomial qui détecte la plus grande union de $k$ sous ensembles convexes discrets de $S\subset \mathbb{Z} ^2$.

A set S⊂Zd is said \emph{digital convex} if \conv(S)∩Zd=S, where \conv(S) denotes the convex hull of S. Herein, we consider several algorithmic problems related to recognition of digital convex sets, as well as the detection of digital convex sets. We start by showing that the quickhull algorithm runs in linear time for digital convex sets. Then, based on this result, we propose an algorithm to test the digital convexiyty of a lattice set S⊂Z2 in O(n+hlogr) time, where h denotes the number of vertices of the convex hull of S, and r denotes the diameter of S. Then, We show how those results can be used to solve the digital polyhedra recognition problem. Finally, we propose a polynomial time algorithm to find the largest union of k digital convex subsets of S⊂Z2., Un ensemble S⊂Zd est \emph{convexe discret} si \conv(S)∩Zd=S, où \conv(S) est l'enveloppe convexe de S. Ici, nous considérons plusieurs problèmes algorithmiques traitant de la reconnaissance d'ensembles convexes discrets ainsi que de la détection de sous ensembles convexes discrets. Nous montrons que l'algorithme quickhull s'exécute en temps linéaire pour des ensembles convexe discret. Puis nous utilisons ce résultat afin de proposer un algorithme qui teste la convexité discrète de S⊂Z2 en O(n+hlogr) temps, où h est le nombre de sommet de l'enveloppe convexe de S et r est le diamètre de S. Ensuite, nous étendons ce résultat et montrons comment il peut être utilisé afin de résoudre le problème de reconnaissance d'ensemble convexe discret. Enfin, nous proposons un algorithme en temps polynomial qui détecte la plus grande union de k sous ensembles convexes discrets de S⊂Z2.

Enseignement Cours et seminaires – Geometrie algorithmique : donnees, modeles, programmes Introduction Le monde numerique n’est maintenant plus limite au texte, au son et aux images, et les representations numeriques de formes tridimensionnelles jouent un role central dans de tres nombreux domaines. Citons, parmi bien d’autres, l’ingenierie, la cartographie, le cinema et les jeux video, l’architecture, la preservation du patrimoine culturel, l’exploration petroliere, la medecine ou encore la ...

3D printers use 3D models in the form of meshes to define the geometry and the appearance of objects to be printed. A 3D mesh must have some topological properties so that the geometry it represents could be printable and the geometry itself must respect certain conditions to be printable. These properties and conditions may vary depending on the 3D printing technologies in use.Many 3D meshes used for printing were not initially designed for this purpose application. The main primary use of these meshes is visualization, which does not require the same topological properties and geometric conditions. The subject of this thesis is the repair of these meshes to make them printable.A repair chain including several steps was designed for this purpose. Non-manifold conditions are repaired by extracting related components (surfaces). The boundaries of surfaces are detected and classified according to the best repair to be applied on each. The boundaries of surfaces are repaired according to their classification either by a filling method or by an offset method. The weakness of the geometry is detected and controlled.; Les imprimantes 3D utilisent des modèles 3D sous la forme de maillages pour définir la géométrie et l'apparence des objets à imprimer. Un maillage 3D doit posséder certaines propriétés topologiques pour que la géométrie qu'il représente soit imprimable, et la géométrie elle même doit respecter certaines conditions pour être imprimable. Ces propriétés et conditions peuvent varier selon la technologie d'impression 3D utilisée.De nombreux maillages 3D utilisés pour l'impression n'ont dans un premier temps pas été conçus pour cette application. La principale utilisation première de ces maillages est la visualisation, qui ne nécessite pas les mêmes propriétés topologiques et conditions géométriques. Le sujet de cette thèse est la réparation de ces maillages afin de les rendre imprimables.Une chaîne de réparation comprenant plusieurs étapes a été conçue dans ce but. Les conditions de non-variété sont réparées en réalisant une extraction de composantes connexes (surfaces). Les bords des surfaces sont détectés et classés en fonction de la meilleure réparation à appliquer sur chaque. Les bords des surfaces sont réparés suivant leurs classement soit par une méthode de remplissage soit par une méthode d'épaississement. La fragilité de la géométrie est détectée et contrôlée.

International audience; A skeleton is a centered geometric representation of a shape that describes the shape in a simple and intuitive way, typically reducing the dimension by at least one. Skeletons are useful in shape analysis and recognition since they provide a framework for part decomposition, are stable under topology preserving deformation, and supply information about the topology and connectivity of the shape. The main drawback to skeletonization algorithms is their sensitivity to small boundary perturbations: noise on a shape boundary, such as pixelation, will produce many spurious branches within a skeleton. As a result, skeletonizations often require a second pruning step. In this article, we propose a new 2D skeletonization algorithm that directly produces a clean skeleton for a shape, avoiding the creation of noisy branches. The approach propagates a circle inside the shape, maintaining neighborhood-based contact with the boundary and bypassing boundary oscillations below a chosen threshold. By explicitly modeling the scale of noise via two parameters that are shape-independent, the algorithm is robust to noise while preserving important shape details. Neither preprocessing of the shape boundary nor pruning of the skeleton is required. Our method produces skeletons with fewer spurious branches than other state-of-the-art methods , while outperforming them visually and according to error measures such as Hausdorff distance and symmetric difference, as evaluated on the MPEG-7 database (1033 images).

3D printers use 3D models in the form of meshes to define the geometry and the appearance of objects to be printed. A 3D mesh must have some topological properties so that the geometry it represents could be printable and the geometry itself must respect certain conditions to be printable. These properties and conditions may vary depending on the 3D printing technologies in use.Many 3D meshes used for printing were not initially designed for this purpose application. The main primary use of these meshes is visualization, which does not require the same topological properties and geometric conditions. The subject of this thesis is the repair of these meshes to make them printable.A repair chain including several steps was designed for this purpose. Non-manifold conditions are repaired by extracting related components (surfaces). The boundaries of surfaces are detected and classified according to the best repair to be applied on each. The boundaries of surfaces are repaired according to their classification either by a filling method or by an offset method. The weakness of the geometry is detected and controlled., Les imprimantes 3D utilisent des modèles 3D sous la forme de maillages pour définir la géométrie et l'apparence des objets à imprimer. Un maillage 3D doit posséder certaines propriétés topologiques pour que la géométrie qu'il représente soit imprimable, et la géométrie elle même doit respecter certaines conditions pour être imprimable. Ces propriétés et conditions peuvent varier selon la technologie d'impression 3D utilisée.De nombreux maillages 3D utilisés pour l'impression n'ont dans un premier temps pas été conçus pour cette application. La principale utilisation première de ces maillages est la visualisation, qui ne nécessite pas les mêmes propriétés topologiques et conditions géométriques. Le sujet de cette thèse est la réparation de ces maillages afin de les rendre imprimables.Une chaîne de réparation comprenant plusieurs étapes a été conçue dans ce but. Les conditions de non-variété sont réparées en réalisant une extraction de composantes connexes (surfaces). Les bords des surfaces sont détectés et classés en fonction de la meilleure réparation à appliquer sur chaque. Les bords des surfaces sont réparés suivant leurs classement soit par une méthode de remplissage soit par une méthode d'épaississement. La fragilité de la géométrie est détectée et contrôlée.

Je souhaite la bienvenue à Jean-Daniel Boissonnat, directeur de recherche de classe résolument exceptionnelle à l’Inria et acteur majeur de la géométrie algorithmique. Ce champ de recherche passionnant de l’informatique regroupe deux mots forts anciens, géométrie et algorithme, qui désignent chacun une discipline dont la racine est antérieure même à la création des mathématiques. Dans son livre Les Métamorphoses du calcul, grand prix 2007 de l’Académie française, Gilles Dowek explique même qu...

The analysis of approximation techniques is a key topic in computational geometry, both for practical and theoretical reasons. In this thesis we discuss sampling tools for geometric structures and geometric approximation algorithms in combinatorial optimization. Part I focuses on the combinatorics of geometric set systems. We start by discussing packing problems in set systems, including extensions of a lemma of Haussler, mainly the so-called shallow packing lemma. For said lemma we also give an optimal lower bound that had been conjectured but not established in previous work on the topic. Then we use this lemma, together with the recently introduced polynomial partitioning technique, to study a combinatorial analogue of the Macbeath regions from convex geometry: Mnets, for which we unify previous existence results and upper bounds, and also give some lower bounds. We highlight their connection with epsilon-nets, staples of computational and combinatorial geometry, for example by observing that the unweighted epsilon-net bound of Chan et al. (SODA 2012) or Varadarajan (STOC 2010) follows directly from our results on Mnets. Part II deals with local-search techniques applied to geometric restrictions of classical combinatorial optimization problems. Over the last ten years such techniques have produced the first polynomial-time approximation schemes for various problems, such as that of computing a minimum-sized hitting set for a collection of input disks from a set of input points. In fact, it was shown that for many of these problems, local search with radius Θ(1/epsilon²) gives a (1 + epsilon)-approximation with running time n^{O(1/epsilon²)}. However the question of whether the exponent of n could be decreased to o(1/epsilon²) was left open. We answer it in the negative: the approximation guarantee of local search cannot be improved for any of these problems. The key ingredient is a new lower bound on locally expanding planar graphs, which is then used to show the impossibility results, L'analyse des techniques d'approximation est centrale en géométrie algorithmique, pour des raisons pratiques comme théoriques. Dans cette thèse nous traitons de l'échantillonnage des structures géométriques et des algorithmes d'approximation géométriques en optimisation combinatoire. La première partie est consacrée à la combinatoire des hypergraphes. Nous débutons par les problèmes de packing, dont des extensions d'un lemme de Haussler, particulièrement le lemme dit de Shallow packing, pour lequel nous donnons aussi un minorant optimal, conjecturé mais pas établi dans les travaux antérieurs. Puis nous appliquons ledit lemme, avec la méthode de partition polynomiale récemment introduite, à l'étude d'un analogue combinatoire des régions de Macbeath de la géométrie convexe : les M-réseaux, pour lesquels nous unifions les résultats d'existence et majorations existants, et donnons aussi quelques minorants. Nous illustrons leur relation aux epsilon-réseaux, structures incontournables en géométrie combinatoire et algorithmique, notamment en observant que les majorants de Chan et al. (SODA 2012) ou Varadarajan (STOC 2010) pour les epsilon-réseaux (uniformes) découlent directement de nos résultats sur les M-réseaux. La deuxième partie traite des techniques de recherche locale appliquées aux restrictions géométriques de problèmes classiques d'optimisation combinatoire. En dix ans, ces techniques ont produit les premiers schémas d'approximation en temps polynomial pour divers problèmes tels que celui de calculer un plus petit ensemble intersectant pour un ensemble de disques donnés en entrée parmi un ensemble de points donnés en entrée. En fait, il a été montré que pour de nombreux tels problèmes, la recherche locale de rayon Θ (1/epsilon²) donne une (1 + epsilon)-approximation en temps n^{O(1/epsilon²)}. Savoir si l'exposant de n pouvait être ramené à o (1/epsilon²) demeurait une question ouverte. Nous répondons par la négative : la garantie d'approximation de la recherche locale n'est améliorable pour aucun desdits problèmes

Describing a complex geometric shape with a set of simple primitives is often a fundamental task for shape reconstruction, visualization, analysis and manipulation. The type of primitives, as well as the choice of approximation scheme, both greatly impact the properties of the resulting shape representation.In this PhD, we focus on balls as primitives. Using pencils of balls, we carefully describe finite unions of balls and their structure. In particular, our description holds in all dimension without assuming general position. On our way, we also establish various results and tools to test local and global inclusions within these unions.We also propose a new approximation scheme by union of balls, the (delta,epsilon)-ball approximation. This scheme constrains the approximation to cover a core subset of the original shape (specifically, an epsilon-erosion), while being contained within a superset of the shape (a delta-dilation). Using our earlier results regarding finite unions of balls, we prove several properties of these approximations. We show that computing a cardinal minimum (delta,epsilon)-ball approximation is an NP-complete problem. For simple planar shapes however, we present a polynomial time and space algorithm that outputs a cardinal minimum approximation. We then conclude by generalizing the approximation scheme to a wider range of core subsets and bounding supersets., Représenter un objet géométrique complexe par un ensemble de primitives simples est une tâche souvent fondamentale, que ce soit pour la reconstruction et la réparation de données, ou encore pour faciliter la visualisation ou la manipulation des données. Le choix de la ou les primitives, ainsi que celui de la méthode d'approximation, impactent fortement les propriétés de la représentation de forme qui sera obtenue.Dans cette thèse, nous utilisons les boules comme seule primitive. Nous prenons ainsi un grand soin à décrire les unions finies de boules et leur structure. Pour cela, nous nous reposons sur les faisceaux de boules. En particulier, nous aboutissons à une description valide en toute dimension, sans hypothèse de position générale. En chemin, nous obtenons également plusieurs résultats portant sur les tests d'inclusion locale et globale dans une union de boules.Nous proposons également une nouvelle méthode d'approximation par union finie de boules, l'approximation par boules à (delta,epsilon)-près. Cette approche contraint l'union de boules à couvrir un sous-ensemble de la forme d'origine (précisément, un epsilon-érodé), tout en étant contenu dans un sur-ensemble de la forme (un delta-dilaté). En nous appuyant sur nos précédents résultats portant sur les unions de boules, nous démontrons plusieurs propriétés de ces approximations. Nous verrons ainsi que calculer une approximation par boules à (delta,epsilon)-près qui soit de cardinal minimum est un problème NP-complet. Pour des formes simples dans le plan, nous présentons un algorithme polynomial en temps et en espace qui permet de calculer ces approximations de cardinal minimum. Nous concluons par une généralisation de notre méthode d'approximation pour une plus large variété de sous-ensembles et sur-ensembles.

In this thesis, we are interested in solving many inverse problems arising inoptics. More precisely, we are interested in designing optical components such as mirrors andlenses that satisfy some light conservation constraints meaning that we want to control thereflected (or refracted) light in order match a prescribed intensity. This has applications incar headlight design or caustic design for example. We show that optical component designproblems can be recast as optimal transport ones for different cost functions and we explainhow this allows to study the existence and the regularity of the solutions of such problems. Wealso show how, using computational geometry, we can use an efficient numerical method namelythe damped Newton’s algorithm to solve all these problems. We will end up with a singlegeneric algorithm able to efficiently build an optical component with a prescribed reflected(or refracted) illumination. We show the convergence of the Newton’s algorithm to solve theoptimal transport problem when the source measure is supported on a finite union of simplices.We then describe the common relation between eight optical component design problemsand show that they can all be seen as discrete Monge-Ampère equations. We also apply theNewton’s method to optical component design and show numerous simulated and fabricatedexamples. Finally, we look at a problem arising in computational optimal transport namelythe choice of the initial weights. We develop three simple procedures to find “good” initialweights which can be used as a starting point in computational optimal transport algorithms., Dans cette thèse, nous nous intéressons à la résolution de nombreux problèmes d’optique anidolique. Plus précisément, il s’agit de construire des composants optiques qui satisfont des contraintes d’illumination à savoir que l’on veut que la lumière réfléchie(ou réfractée) par ce composant corresponde à une distribution fixée en avance. Comme applications, nous pouvons citer la conception de phares de voitures ou de caustiques. Nous montrons que ces problèmes de conception de composants optiques peuvent être vus comme des problèmes de transport optimal et nous expliquons en quoi cette formulation permet d’étudier l’existence et la régularité des solutions. Nous montrons aussi comment, en utilisant des outils de géométrie algorithmique, nous pouvons utiliser une méthode numérique efficace, la méthode de Newton amortie, pour résoudre tous ces problèmes. Nous obtenons un algorithme générique capable de construire efficacement un composant optique qui réfléchit (ou réfracte)une distribution de lumière prescrite. Nous montrons aussi la convergence de l’algorithme de Newton pour résoudre le problème de transport optimal dans le cas où le support de la mesure source est une union finie de simplexes. Nous décrivons également la relation commune qui existe entre huit différents problèmes de conception de composants optiques et montrons qu’ils peuvent tous être vus comme des équations de Monge-Ampère discrètes. Nous appliquons aussi la méthode de Newton à de nombreux problèmes de conception de composants optiques sur différents exemples simulés ainsi que sur des prototypes physiques. Enfin, nous nous intéressons à un problème apparaissant en transport optimal numérique à savoir le choix du point initial. Nous développons trois méthodes simples pour trouver de “bons” points initiaux qui peuvent être ensuite utilisés comme point de départ dans des algorithmes de résolution de transport optimal.

The cumulative stack-up of geometric variations in mechanical systems can be modelled summing and intersecting sets of constraints. These constraints derive from tolerance zones or from contact restrictions between parts. The degrees of freedom (DOF) of jointsgenerate unbounded sets (i.e. polyhedra) which are difficult to deal with. L. Homri presented in 2014 a solution based on the setting of fictitious limits (called cap constraints) to each DOFto obtain bounded 6D sets (i.e. polytopes). These additional constraints, however, increase the complexity of the models, and therefore, of the computations. In response to this situation,we defined a derived strategy to control the effects of the propagation of the fictitious limits by tracing and simplifying the generated, new cap constraints. We proposed a second strategy based on the decomposition of polyhedra into the sum of a polytope and a set of straight lines.The strategy consists in isolating the straight lines (associated to the DOF) and summing the polytopes in the smallest sub-space. After solving an industrial case, we concluded that tracing caps constraints during the operations allows reducing the models complexity and,consequently, the computational time; however, it still involves working in 6d even in caseswhere this is not necessary. In contrast, the strategy based on the operands decompositionis more efficient due to the dimension reduction. This study allowed us to conclude that the management of mechanisms’ mobility is a crucial aspect in tolerance simulations. The gain on efficiency resulting from the developed strategies opens up the possibility for doing statistical treatment of tolerances and tolerance synthesis.; L’analyse de tolérances par des ensembles de contraintes repose sur la détermination de l’accumulation de variations géométriques par des sommes et intersections d’ensembles opérandes 6d. Les degrés de liberté des liaisons et les degrés d’invariance des surfaces génèrent des opérandes non-bornés (polyèdres), posant des problèmes de simulation. En 2014, L. Homria proposé une méthode pour résoudre ce problème, consistant à ajouter des limites artificielles(contraintes bouchon) sur les déplacements non-bornés. Même si cette méthode permet la manipulation d’objets bornés (polytopes), les contraintes bouchon augmentent la complexité des simulations. En réponse à cette difficulté, une méthode dérivée est proposée dans cette thèse.Cette méthode consiste à tracer et simplifier les contraintes bouchon au travers des opérations.Puis une seconde stratégie basée sur la décomposition d’un polyèdre en une somme d’un polytope et de lignes droites (associées aux déplacements non-bornés). Cette stratégie consiste à simuler d’une part les sommes de droites, et d’autre part, à déterminer la somme de polytopes dans un sous-espace de dimension inférieur à 6. Ces trois stratégies sont comparées au travers d’une application industrielle. Cela montre que la traçabilité des contraintes bouchons est un aspect fondamental pour contrôler leur propagation et pour réduire le temps de calcul des simulations. Toutefois, cette méthode exige encore de déterminer les limites des déplacements non-bornés. La deuxième méthode, adaptant systématiquement la dimension de l’espace de calcul, elle permet de diminuer davantage le temps de calcul. Ce travail permet d’envisager la mise en oeuvre de cette méthode selon des formulations statistiques avec la prise en compte des défauts de forme des surfaces.

The cumulative stack-up of geometric variations in mechanical systems can be modelled summing and intersecting sets of constraints. These constraints derive from tolerance zones or from contact restrictions between parts. The degrees of freedom (DOF) of jointsgenerate unbounded sets (i.e. polyhedra) which are difficult to deal with. L. Homri presented in 2014 a solution based on the setting of fictitious limits (called cap constraints) to each DOFto obtain bounded 6D sets (i.e. polytopes). These additional constraints, however, increase the complexity of the models, and therefore, of the computations. In response to this situation,we defined a derived strategy to control the effects of the propagation of the fictitious limits by tracing and simplifying the generated, new cap constraints. We proposed a second strategy based on the decomposition of polyhedra into the sum of a polytope and a set of straight lines.The strategy consists in isolating the straight lines (associated to the DOF) and summing the polytopes in the smallest sub-space. After solving an industrial case, we concluded that tracing caps constraints during the operations allows reducing the models complexity and,consequently, the computational time; however, it still involves working in 6d even in caseswhere this is not necessary. In contrast, the strategy based on the operands decompositionis more efficient due to the dimension reduction. This study allowed us to conclude that the management of mechanisms’ mobility is a crucial aspect in tolerance simulations. The gain on efficiency resulting from the developed strategies opens up the possibility for doing statistical treatment of tolerances and tolerance synthesis., L’analyse de tolérances par des ensembles de contraintes repose sur la détermination de l’accumulation de variations géométriques par des sommes et intersections d’ensembles opérandes 6d. Les degrés de liberté des liaisons et les degrés d’invariance des surfaces génèrent des opérandes non-bornés (polyèdres), posant des problèmes de simulation. En 2014, L. Homria proposé une méthode pour résoudre ce problème, consistant à ajouter des limites artificielles(contraintes bouchon) sur les déplacements non-bornés. Même si cette méthode permet la manipulation d’objets bornés (polytopes), les contraintes bouchon augmentent la complexité des simulations. En réponse à cette difficulté, une méthode dérivée est proposée dans cette thèse.Cette méthode consiste à tracer et simplifier les contraintes bouchon au travers des opérations.Puis une seconde stratégie basée sur la décomposition d’un polyèdre en une somme d’un polytope et de lignes droites (associées aux déplacements non-bornés). Cette stratégie consiste à simuler d’une part les sommes de droites, et d’autre part, à déterminer la somme de polytopes dans un sous-espace de dimension inférieur à 6. Ces trois stratégies sont comparées au travers d’une application industrielle. Cela montre que la traçabilité des contraintes bouchons est un aspect fondamental pour contrôler leur propagation et pour réduire le temps de calcul des simulations. Toutefois, cette méthode exige encore de déterminer les limites des déplacements non-bornés. La deuxième méthode, adaptant systématiquement la dimension de l’espace de calcul, elle permet de diminuer davantage le temps de calcul. Ce travail permet d’envisager la mise en oeuvre de cette méthode selon des formulations statistiques avec la prise en compte des défauts de forme des surfaces.

Geographic Information System (GIS) and computational geometry are source for many geometric issues. Among issues addressed is the need to get a mesh representation which can enable to enhance the computation of surface flows in hydrologic and digital terrain models. Delaunay triangulation emerges to be an efficient tool because of its useful properties: realistic physical representation taking into account topological, geometrical and morphometric properties; the flux across any edge with its neighbors is always normal to its boundary by definition and thus reduces the computational cost to evaluate flux across the volume boundary. In this paper, issues concerning GIS and computational geometry is first presented. Then, we propose an application for urban modeling integrating terrain modeling based on Delaunay triangulation that can be used as support for flood simulation and bulding modeling., Les systèmes d'information géographiques (SIG) et la géométrie algorithmique sont à l'ori-ginique de beaucoup de problèmes associés à la représentation géométrique. Parmi ces problèmes figurent le besoin d'avoir un maillage qui permet d'améliorer le calcul de l'écoulement hydrologique sur la surface et les modèles numériques de terrain. La triangulation de Delaunay est un outil efficace à cause de ces propriètés intrinsèques (topologiques,géométriques et morphologiques) qui sont prises en compte lors de la construction du maillage afin d'aboutir à une représentation plus réaliste et à la réduction du coup de calcul pour évaluer le flux aux bords. Dans ce travail, nous présentons d'abord quelques problématiques liées a la géométriqe algorithmique et au GIS et ensuite nous propososons un modèle de description urbaine pour la simulation d'inondation intégrant un modèle numérique de terrain basé sur la triangulation de Delaunay et un modèle de bâtiments.

Geographic Information System (GIS) and computational geometry are source for many geometric issues. Among issues addressed is the need to get a mesh representation which can enable to enhance the computation of surface flows in hydrologic and digital terrain models. Delaunay triangulation emerges to be an efficient tool because of its useful properties: realistic physical representation taking into account topological, geometrical and morphometric properties; the flux across any edge with its neighbors is always normal to its boundary by definition and thus reduces the computational cost to evaluate flux across the volume boundary. In this paper, issues concerning GIS and computational geometry is first presented. Then, we propose an application for urban modeling integrating terrain modeling based on Delaunay triangulation that can be used as support for flood simulation and bulding modeling., Les systèmes d'information géographiques (SIG) et la géométrie algorithmique sont à l'ori-ginique de beaucoup de problèmes associés à la représentation géométrique. Parmi ces problèmes figurent le besoin d'avoir un maillage qui permet d'améliorer le calcul de l'écoulement hydrologique sur la surface et les modèles numériques de terrain. La triangulation de Delaunay est un outil efficace à cause de ces propriètés intrinsèques (topologiques,géométriques et morphologiques) qui sont prises en compte lors de la construction du maillage afin d'aboutir à une représentation plus réaliste et à la réduction du coup de calcul pour évaluer le flux aux bords. Dans ce travail, nous présentons d'abord quelques problématiques liées a la géométriqe algorithmique et au GIS et ensuite nous propososons un modèle de description urbaine pour la simulation d'inondation intégrant un modèle numérique de terrain basé sur la triangulation de Delaunay et un modèle de bâtiments.

Real-world data has a large geometric component, showing significant geometric patterns. How to use the geometric nature of data to design efficient methods has became a very important topic in several scientific fields, e.g., computational geometry, discrete geometry, computer graphics, computer vision. In this thesis we use geometric structures to design efficient algorithms for problems in two domains, computer graphics and combinatorial optimization. Part I focuses on a geometric data structure called well-separated pair decomposition and its usage for one of the most challenging problems in computer graphics, namely efficient photo-realistic rendering. One solution is the family of many-lights methods that approximate global illumination by individually computing illumination from a large number of virtual point lights (VPLs) placed on surfaces. Considering each VPL individually results in a vast number of calculations. One successful strategy the reduce computations is to group the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. We use the well-separated pair decomposition of points as a basis for a data structure for pre-computing and compactly storing a set of view independent candidate VPL clusterings showing that a suitable clustering of the VPLs can be efficiently extracted from this data structure. We show that instead of clustering points and/or VPLs independently what is required is to cluster the product-space of the set of points to be shaded and the set of VPLs based on the induced pairwise illumination. Additionally we propose an adaptive sampling technique to reduce the number of visibility queries for each product-space cluster. Our method handles any light source that can be approximated with virtual point lights (VPLs), highly glossy materials and outperforms previous state-of-the-art methods. Part II focuses on developing new approximation algorithms for a fundamental NP-complete problem in computational geometry, namely the minimum hitting set problem with particular focus on the case where given a set of points and a set of disks, we wish to compute the minimum-sized subset of the points that hits all disks. It turns out that efficient algorithms for geometric hitting set rely on a key geometric structure, called epsilon-net. We give an algorithm that uses only Delaunay triangulations to construct epsilon-nets of size 13.4/epsilon and we provide a practical implementation of a technique to calculate hitting sets in near-linear time using small sized epsilon-nets. Our results yield a 13.4 approximation for the hitting set problem with an algorithm that runs efficiently even on large data sets. For smaller datasets, we present an implementation of the local search technique along with tight approximation bounds for its approximation factor, yielding an (8 + epsilon)-approximation algorithm with running time O(n^{2.34}), Les données du monde réel ont manifestement une composante géométrique importante et suggère les patterns géométriques signifiants. Les méthodes qui utilisent la nature géométrique des données sont activement développés dans plusieurs domaines scientifiques, comme, par exemple, la géométrie algorithmique, la géométrie discrète, la synthèse d'images, la vision par ordinateur. Dans le travail présent, nous utilisons les structures géométriques afin de modéliser des algorithmes efficaces pour deux domaines, celui de synthèse d'images et de l'optimisation combinatoire. Dans la première partie il s'agit de la structure de données géométriques, appelé une décomposition bien-séparée, et son application pour un des problèmes les plus difficiles dans la synthèse d'images, un efficace rendu photo-réalistique. Une solution consiste à appliquer toute une famille de méthodes de many-lights qui fait une approximation d'illumination globale par calcule individuelle d'illumination avec un grand nombre de VPLs (virtual point light) répartis sur les surfaces. L'application individuelle de chacun VPL résulte dans un grand nombre des calculs. Une des stratégies de la réussite pour réduire les computations est de faire les clusteurs considérés qui sont consideré comme une seul émetteur. Nous utilisons la décomposition bien-séparée de points comme le fondement de la structure des données susceptible de procéder à un calcul préliminaire et de conserver d'une façon compacte un grand nombre des clusterisations individuels potentiels ce qui montre que la clusterisation des VPL plus correspondante peut être extraite de cette structure de données d'une manière efficace. Nous montrons qu'au lieu de regroupper les points et/ou VPL indépendemment il vaut mieux produire les clusteurs sur l'espace de produit du nombre des points à nuancer et un groupe de VPL à la base de l'illumination des paires induite. En plus, nous proposons une technique adaptive afin d'échantillonner pour réduire le nombre des demandes de vérifications de visibilité pour chaque clusteur de l'espace de produit. Notre méthode consiste à détenir chaque émetteur qui peut être rapproché par VPL, matériaux spéculaire et à performer les méthodes précédents réconnus les meilleurs jusqu'au présent. La deuxième partie est consacrée au développement de nouveaux algorithmes d'approximation pour un problème fondamental de NP complet dans la géométrie algorithmique, précisément le problème du hitting set, avec une précision pour le cas d'un groupe de points et d'un groupe de disques, nous souhaiterons calculer les plus petits nombre du points qui touche tous les disques. Il arrive que les algorithmes efficaces à détecter le hitting set repose sur une structure géométrique clée, appelée epsilon-net. Nous donnons un algorithme utilisant uniquement les triangulisations de Delaunay pour construire les epsilon-nets de taille 13.4/epsilon. Nous donnons une implémentation pratique de la technique à calculer les hitting sets dans le temps quasi-linéaire en utilisant des epsilon-nets de petites tailles. Nos résultats aboutissent à une approximation de 13.4 pour le problème de hitting set par un algorithme qui fonctionne même pour les grands ensembles de données. Pour les ensembles de taille plus petite, nous proposons une implémentation de la technique de recherche locale avec une approximation bornes supérieures, avec le résultat obtenu d'approximation de (8 + epsilon) dans le temps O(n^{2.34})

This paper delves into the problem of detecting the intersection of two convexpolyhedra.It does so through the lens of Minkowski sums and Gauss maps, and with a biastowards applications in computer graphics and robotics.In the first part, we show how Minkowski sums and Gauss maps come into play,give a brief survey of techniques for pairs of simple shapes and describe alow-level optimization of a naive algorithm for convex polyhedra, which isapplied to tetrahedra.Novel applications to the ray casting problem are also given.In the second part, we take a more abstract approach to the problem anddescribe a new and very efficient and robust algorithm for detecting theintersection of two convex shapes.The new technique works directly on the unit sphere, interpreted as the sphereof directions.In particular, it is compared favourably to the ubiquitous algorithm ofGilbert, Johnson and Keerthi.; Cet article discute du problème (décisionnel) de la détection de l'intersectionde deux polyèdres convexes. Il porte particulièrement sur les applications dece problème en informatique graphique et en robotique. La discussion s'y faitdu point de vue des sommes de Minkoswki et de l'application de Gauss.Dans la première partie, nous rappellons le rôle de ce point de vue dans lacompréhension de la géométrie du problème. Nous donnons un bref aperçu destechniques conçues pour certaines paires de formes simples, et nous proposonsun algorithme naïf mais optimisé, traitant des polyèdres convexes quelconques.Nous traitons en exemple une application aux paires de tétraèdres et uneapplication au problème du lancer de rayons.En deuxième partie, nous approchons le problème de manière plus abstraite etdécrivons un nouvel algorithme robuste et rapide pour la détection del'intersection de deux objets convexes (non nécessairement polyédrique).Ce nouvel algorithme travaille directement sur la sphère unité que nousinterprétons comme l'espace des directions. En particulier, notre nouvelletechnique est comparée favorablement à celle, fort répandue, de Gilbert,Johnson et Keerthi.

This paper delves into the problem of detecting the intersection of two convexpolyhedra.It does so through the lens of Minkowski sums and Gauss maps, and with a biastowards applications in computer graphics and robotics.In the first part, we show how Minkowski sums and Gauss maps come into play,give a brief survey of techniques for pairs of simple shapes and describe alow-level optimization of a naive algorithm for convex polyhedra, which isapplied to tetrahedra.Novel applications to the ray casting problem are also given.In the second part, we take a more abstract approach to the problem anddescribe a new and very efficient and robust algorithm for detecting theintersection of two convex shapes.The new technique works directly on the unit sphere, interpreted as the sphereof directions.In particular, it is compared favourably to the ubiquitous algorithm ofGilbert, Johnson and Keerthi.; Cet article discute du problème (décisionnel) de la détection de l'intersectionde deux polyèdres convexes. Il porte particulièrement sur les applications dece problème en informatique graphique et en robotique. La discussion s'y faitdu point de vue des sommes de Minkoswki et de l'application de Gauss.Dans la première partie, nous rappellons le rôle de ce point de vue dans lacompréhension de la géométrie du problème. Nous donnons un bref aperçu destechniques conçues pour certaines paires de formes simples, et nous proposonsun algorithme naïf mais optimisé, traitant des polyèdres convexes quelconques.Nous traitons en exemple une application aux paires de tétraèdres et uneapplication au problème du lancer de rayons.En deuxième partie, nous approchons le problème de manière plus abstraite etdécrivons un nouvel algorithme robuste et rapide pour la détection del'intersection de deux objets convexes (non nécessairement polyédrique).Ce nouvel algorithme travaille directement sur la sphère unité que nousinterprétons comme l'espace des directions. En particulier, notre nouvelletechnique est comparée favorablement à celle, fort répandue, de Gilbert,Johnson et Keerthi.

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., 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 this paper, we show that, amongst $n$ uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal nonoccluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene, providing evidence that the storage requirement for this data structure is not necessarily prohibitive. These results significantly improve the best previously known bounds of $O(n^{8/3})$ [F. Durand, G. Drettakis, and C. Puech, {ACM Transactions on Graphics}, 21 (2002), pp. 176--206]. Our results generalize in various directions. We show that the linear bound on the expected number of maximal nonoccluded line segments that are not too close to the boundary of the scene and tangent to four unit balls extends to balls of various but bounded radii, to polyhedra of bounded aspect ratio, and even to nonfat three-dimensional objects such as polygons of bounded aspect ratio. We also prove that our results extend to other distributions such as the Poisson distribution. Finally, we indicate how our probabilistic analysis provides new insight on the expected size of other global visibility data structures, notably the aspect graph.

International audience; Graph Visualization is a technique that helps users to easily comprehend connected data (social networks, semantic networks, etc.) based on human perception. With the prevalence of Big Data, these graphs tend to be too large to decipher by the user’s visual abilities alone. One of the leading causes of this problem is when the nodes leave the visualization space. Many attempts have been made to optimize large graph visualization, but they all have limitations. Among these attempts, the most famous one is the Force Directed Placement Algorithm. This algorithm can provide beautiful visualizations for small to medium graphs, but when it comes to larger graphs it fails to keep some independent nodes or even subgraphs inside the visualization space. In this paper, we present an algorithm that we have named "Forced Force Directed Placement". This algorithm provides an enhancement of the classical Force Directed Placement algorithm by proposing a stronger force function. The “FForce”, as we have named it, can bring related nodes closer to each other before reaching an equilibrium position. This helped us gain more display space and that gave us the possibility to visualize larger graphs.

This habilitation thesis proposes a series of contributions in the field of geometric modeling from physical measurements. These contributions present concepts and algorithms for object extraction, surface reconstruction, and scene modeling for urban environments. The methodology behind these contributions relies on stochastic geometry and graphical models. These probabilistic models are suited to analyzing the diversity and the complexity of urban objects and to exploring large and highly non-convex solution spaces at city-scales. The physical measurements, data structures, and concepts involved in our work lie between computer vision, geometry processing, and photogrammetry. A general summary also provides a vision of the many remaining challenges in the field.

The digital mock-up (DMU) of a product has taken a central position in the product development process (PDP). It provides the geometric reference of the product assembly, as it defines the shape of each individual component, as well as the way components are put together. However, observations show that this geometric model is no more than a conventional representation of what the real product is. Additionally, and because of its pivotal role, the DMU is more and more required to provide information beyond mere geometry to be used in different stages of the PDP. An increasingly urging demand is functional information at different levels of the geometric representation of the assembly. This information is shown to be essential in phases such as geometric pre-processing for finite element analysis (FEA) purposes. In this work, an automated method is put forward that enriches a geometric model, which is the product DMU, with function information needed for FEA preparations. To this end, the initial geometry is restructured at different levels according to functional annotation needs. Prevailing industrial practices and representation conventions are taken into account in order to functionally interpret the pure geometric model that provides a start point to the proposed method.; La maquette numérique d'un produit occupe une position centrale dans le processus de développement de produit. Elle est utilisée comme représentation de référence des produits, en définissant la forme géométrique de chaque composant, ainsi que les représentations simplifiées des liaisons entre composants. Toutefois, les observations montrent que ce modèle géométrique n'est qu'une représentation simplifiée du produit réel. De plus, et grâce à son rôle clé, la maquette numérique est de plus en plus utilisée pour structurer les informations non-géométriques qui sont ensuite utilisées dans diverses étapes du processus de développement de produits. Une demande importante est d'accéder aux informations fonctionnelles à différents niveaux de la représentation géométrique d'un assemblage. Ces informations fonctionnelles s'avèrent essentielles pour préparer des analyses éléments finis. Dans ce travail, nous proposons une méthode automatisée afin d'enrichir le modèle géométrique extrait d'une maquette numérique avec les informations fonctionnelles nécessaires pour la préparation d'un modèle de simulation par éléments finis. Les pratiques industrielles et les représentations géométriques simplifiées sont prises en compte lors de l'interprétation d'un modèle purement géométrique qui constitue le point de départ de la méthode proposée.

International audience; Efficient sampling from high-dimensional distribu- tions is a challenging issue that is encountered in many large data recovery problems. In this context, sampling using Hamil- tonian dynamics is one of the recent techniques that have been proposed to exploit the target distribution geometry. Such schemes have clearly been shown to be efficient for multidimensional sam- pling but, rather, are adapted to distributions from the exponential family with smooth energy functions. In this paper, we address the problem of using Hamiltonian dynamics to sample from probabil- ity distributions having non-differentiable energy functions such as those based on the l1 norm. Such distributions are being used intensively in sparse signal and image recovery applications. The technique studied in this paper uses a modified leapfrog transform involving a proximal step. The resulting nonsmooth Hamiltonian Monte Carlo method is tested and validated on a number of exper- iments. Results show its ability to accurately sample according to various multivariate target distributions. The proposed technique is illustrated on synthetic examples and is applied to an image denoising problem.

The digital mock-up (DMU) of a product has taken a central position in the product development process (PDP). It provides the geometric reference of the product assembly, as it defines the shape of each individual component, as well as the way components are put together. However, observations show that this geometric model is no more than a conventional representation of what the real product is. Additionally, and because of its pivotal role, the DMU is more and more required to provide information beyond mere geometry to be used in different stages of the PDP. An increasingly urging demand is functional information at different levels of the geometric representation of the assembly. This information is shown to be essential in phases such as geometric pre-processing for finite element analysis (FEA) purposes. In this work, an automated method is put forward that enriches a geometric model, which is the product DMU, with function information needed for FEA preparations. To this end, the initial geometry is restructured at different levels according to functional annotation needs. Prevailing industrial practices and representation conventions are taken into account in order to functionally interpret the pure geometric model that provides a start point to the proposed method., La maquette numérique d'un produit occupe une position centrale dans le processus de développement de produit. Elle est utilisée comme représentation de référence des produits, en définissant la forme géométrique de chaque composant, ainsi que les représentations simplifiées des liaisons entre composants. Toutefois, les observations montrent que ce modèle géométrique n'est qu'une représentation simplifiée du produit réel. De plus, et grâce à son rôle clé, la maquette numérique est de plus en plus utilisée pour structurer les informations non-géométriques qui sont ensuite utilisées dans diverses étapes du processus de développement de produits. Une demande importante est d'accéder aux informations fonctionnelles à différents niveaux de la représentation géométrique d'un assemblage. Ces informations fonctionnelles s'avèrent essentielles pour préparer des analyses éléments finis. Dans ce travail, nous proposons une méthode automatisée afin d'enrichir le modèle géométrique extrait d'une maquette numérique avec les informations fonctionnelles nécessaires pour la préparation d'un modèle de simulation par éléments finis. Les pratiques industrielles et les représentations géométriques simplifiées sont prises en compte lors de l'interprétation d'un modèle purement géométrique qui constitue le point de départ de la méthode proposée.

This habilitation thesis proposes a series of contributions in the field of geometric modeling from physical measurements. These contributions present concepts and algorithms for object extraction, surface reconstruction, and scene modeling for urban environments. The methodology behind these contributions relies on stochastic geometry and graphical models. These probabilistic models are suited to analyzing the diversity and the complexity of urban objects and to exploring large and highly non-convex solution spaces at city-scales. The physical measurements, data structures, and concepts involved in our work lie between computer vision, geometry processing, and photogrammetry. A general summary also provides a vision of the many remaining challenges in the field.

Defining shapes by iteration allows us to generate new structures with specific properties (roughness,lacunarity), which cannot be achieved with classic modelling.For developing an iterative modeller to design fractals described by a BCIFS, we developed a set oftools and algorithms that permits one to evaluate, to characterize and to analyse different geometricproperties (localisation, convex hull, volume, fractal dimension) of fractals. We identified properties ofstandard CAD operations (intersection, union, offset, . . . ) allowing us to approximate them for fractalsand also to optimize these approximation algorithms.In some cases, it is possible to construct a CIFS with generalised HUTCHINSON operator, whoseattractor is close enough to the operation result with respect to the HAUSDORFF metric.We introduceda generic algorithm to compute such CIFS for a given accuracy.We defined the self-similarity propertyof the operation defining a set of transformations, which are used in the output iterative system.In order to construct an exact CIFS of the image, if it exists, we must prove all the necessarysimilarities manually. We explicit also the condition of the operation to be represented by an IFS witha generalised HUTCHINSON operator. In this case, only this condition should be proved manually, La définition de formes par ces procédés itératifs génère des structures avec des propriétésspécifiques intéressantes : rugosité, lacunarité. . . . Cependant, les modèles géométriques classiquesne sont pas adaptés à la description de ces formes.Dans le but de développer un modeleur itératif pour concevoir des objets fractals décrits à l’aide duBCIFS, nous avons développé un ensemble d’outils et d’algorithmes génériques qui nous permettentd’évaluer, de caractériser et d’analyser les différentes propriétés géométriques (la localisation, lecalcul de l’enveloppe convexe, de la distance à partir d’un point, etc) de fractals. Nous avons identifiéles propriétés des opérations standards (intersection, union, offset, . . . ) permettant de calculer uneapproximation d’image des fractales et de plus d’optimiser ces algorithmes d’approximation.Dans certains cas, il est possible de construire un CIFS avec l’opérateur de HUTCHINSON généralisédont l’attracteur est suffisamment proche du résultat de l’opération par rapport à la métrique deHausdorff. Nous avons développé un algorithme générique pour calculer ces CIFS pour une précisiondonnée. Nous avons défini la propriété d’auto-similarité de l’opération, qui définie un ensemble detransformations utilisé dans un système itératif résultant.Pour construire un CIFS exact de l’image, si il existe, il faut prouver tous les similitudes nécessairesmanuellement. Nous explicitons également la condition de l’opération, quand le résultat peut êtrereprésenté par un IFS avec un opérateur de HUTCHINSON généralisé. Dans ce cas, il n’est que cettecondition à prouver manuellement

The development of scanning 3D shapes (national heritage conservation, ecommerce, reverse engineering, virtual reality environments) and the growing need for geometric objects in many applications (computer-aided design, simulations, geographic information systems, digital entertainment) have led to a dramatic increase in the volume of data to be processed, and the emergence of many methods of compression of 3D models. This volume of data becomes even more difficult to control when the temporal aspect comes in. Meshes correspond to the pattern typically used to model the scanned forms and some approaches exploit a property of compression that a good estimation of connectivity can be derived from sampling, when it appears sufficiently dense. Compressing the connectivity of a mesh is equivalent to coding the difference between two close connectivities. In this thesis, we focus on the compact coding of this difference for 2-dimensional meshes. Our work is based on the use and study of the properties of the edge flip. Our contributions are the following : - Given two connected triangulations that share the same number of vertices and the same topological genus, we propose a direct and efficient algorithm to generate a sequence of edge flips to change one mesh into the other. We rely on a correspondence between the vertices of the two meshes, which, if not provided, may be chosen randomly. The validity of the algorithm is based on the fact that we intend to work in a triangulation of a different class from those generally used. - We then generalize the edge flips to triangulations in which we identify each edge with a label. We show that a sequence of edge flips can be used to transpose two labels, under certain conditions. From this result, the edge flip can be generalized to meshes whose faces are not necessarily triangular, which allowed us to develop an algorithm for reducing sequences of edge flips. - Finally, we present a compact coding approach for a sequence of edge flips, and determine under what conditions it is better to use this compact transformation between two connectivities instead of coding them independently by a static algorithm, Le développement de la numérisation systématique des formes 3D (conservation du patrimoine national, commerce électronique, reverse engineering, intégration d’objets réels dans des environnements de réalité virtuelle) et le besoin toujours croissant de ces objets géométriques dans de nombreuses applications (conception assistée par ordinateur, calcul de simulations par éléments finis, système d’informations géographiques, loisirs numériques) a entrainé une augmentation vertigineuse du volume de données à traiter, avec l’émergence de nombreuses méthodes de compression de modèles 3D. Ce volume de données devient encore plus difficile à maitriser lorsque l’aspect temporel entre en jeu. Les maillages correspondent au modèle classiquement utilisé pour modéliser les formes numérisées et certaines approches de compression exploitent la propriété qu’une bonne estimation de la connectivité peut être déduite de l’échantillonnage, lorsque ce dernier s’avère suffisamment dense. La compression de la connectivité d’un maillage revient alors au codage de l’écart entre deux connectivités proches. Dans ce mémoire, nous nous intéressons au codage compact de cette différence pour des maillages surfaciques. Nos travaux sont fondés sur l’utilisation de la bascule d’arête (edge flip) et l’étude de ses propriétés. Nos contributions sont les suivantes. Etant donné deux triangulations connexes partageant le même nombre de sommets et un même genre topologique, nous proposons un algorithme direct et efficace pour générer une séquence de bascules d’arêtes permettant de passer d’un maillage `a un autre. Nous nous appuyons sur une correspondance entre les sommets des deux maillages, qui, si elle est non fournie, peut être choisie de manière totalement aléatoire

To target more profitable oil and gas deposits, the numerical simulation is of growing interest in the oil sector. In this context, two main types of applications are distinguished: reservoir engineering where geological models are defined as static and exploration for the simulation of hydrocarbons formation. The latter application requires dynamic basins models. For this type of simulation, mathematical and numerical modeling has been an important advance in recent years. However, the construction of meshes needed for the simulations is a difficult task in the case of complex and dynamic geometries. The difficulty is reflected by the characteristic of the domain to mesh, which is defined from the mechanics of granular media which are almost incompressible and heterogeneous environments. In addition, the seismic data represent non-implicit surfaces modeling volume blocks. In this context, we focus on Lagrangian hex-dominant mesh generation of basins with complex geometry. The desired mesh must contain a layer of almost hexahedral meshes between two horizons and conform to fault surfaces through these horizons. A novel methodology based on the construction of an unfolded space is introduced. The desired mesh is then seen as a constrained 3D grid in this novel space. Several mesh optimization techniques are also proposed, Afin de cibler une meilleure rentabilité des gisements d'hydrocarbures, la simulation numérique présente un intérêt grandissant dans le secteur pétrolier. Dans ce contexte, deux principaux types d'applications sont distingués : l'ingénierie du réservoir, où les modèles géologiques sont définis comme statiques et l'exploration des gisements par la simulation de la formation des hydrocarbures. Cette dernière application nécessite des modèles de bassins dynamiques. Pour ce type de simulation, la modélisation mathématique et numérique a connu une avancée importante durant les dernières années. En revanche, la construction de maillages indispensables pour les simulations reste une tâche lourde dans le cas de géométries complexes et dynamiques. La difficulté se traduit par la particularité du domaine à mailler, qui est dictée par la mécanique des milieux granulaires, c'est-à-dire des milieux quasi-incompressibles et hétérogènes. De plus, les données sismiques sont des surfaces non-implicites modélisant des blocs volumiques. Dans ce cadre, nous nous intéressons à la génération de maillages lagrangiens hexa-dominants des bassins à géométrie complexe. Le maillage souhaité doit contenir une couche de mailles principalement hexaédriques entre deux horizons et respecter les surfaces failles traversant ces horizons. Une méthodologie originale basée sur la construction d’un espace déplié est proposée. Le maillage souhaité est alors traduit par une grille 3D contrainte dans cet espace. Plusieurs techniques d’optimisation de maillages sont aussi proposées

L'analyse des tolérances géométriques d'un système mécanique consiste à simuler la vérification de la conformité d'un système mécanique au regard des exigences fonctionnelles caractérisant le fonctionnement attendu du système. Cette vérification impose de prendre en compte les spécifications géométriques des pièces constitutives et les spécifications entre les pièces potentiellement en contact.Je me suis plus particulièrement focalisé sur la simulation de l'analyse des tolérances géométriques par une approche variationnelle (collaboration laboratoire MAP5, Université Paris Descartes). Une approche variationnelle consiste à ne manipuler que des contraintes caractérisant les variations géométriques entre des surfaces d'une même pièce et entre des surfaces de pièces potentiellement en contact. Cela permet de modéliser la variabilité des défauts géométriques inhérents à tout procédé de fabrication de pièces, inhérents à tout procédé d’assemblage et aussi inhérent au comportement d’un système mécanique, par exemple son comportement thermomécanique (thèse Laurent Pierre). La conformité d'un système mécanique doit être assurée pour plusieurs exigences fonctionnelles. D'autre part, une démarche d'analyse de tolérances réalisées à un stade très avancé du cycle de conception peut constater des non conformités sans pour autant influencer les différents choix d'architectures d'un système, ainsi que les formes et dimensions des pièces constitutives. Ce problème est souvent la cause de l'augmentation des délais et des coûts de développement d'un produit.Cela m'a conduit à m'orienter vers la structuration des données pour le tolérancement dans un modèle produit pour identifier les données manipulées en analyse de tolérances (thèse Jérôme Dufaure). La formalisation d'une activité de transfert de spécifications géométriques a mis en évidence la nécessité d'assurer la traçabilité des spécifications géométriques pour : couvrir le cycle de conception (aspect multi niveaux du cycle de conception d'un produit) partager les données manipulées avec d'autres expertises métiers (aspect multi vues du cycle de conception d'un produit). Le transfert d'une exigence fonctionnelle doit donc être réalisé à travers différents niveaux de détails du produit (transfert interniveaux) et également entre différentes expertises métiers liés à la fabrication, l'assemblage et la métrologie (transfert intervues). Une tentative d'extension des concepts de transfert de spécifications techniques liées au produit sur des spécifications organisationnelles inhérentes à l'entreprise assurant la conception du produit a été réalisée (thèse manuel Gonçalves). Enfin, une opportunité industrielle fortement stimulée par le contexte aquitain incitant les acteurs du pôle Aerospace Valley à développer des compétences liées aux matériaux composites, m'a conduit à aborder la problématique d'analyse de tolérances pour la fabrication liée au procédé Resin Transfer Molding (RTM) (thèse Serge Mouton). Dans un procédé impliquant des phénomènes physiques extrêmement complexes, les spécifications fonctionnelles d'une pièce de structure aéronautique ont été corrélés à des spécifications de fabrication (spécifications d'outillages, spécifications de pression d'injection et de température ...). Dans ce type travail, il n'est plus possible de travailler avec des modèles de solides infiniment rigides comme souvent en tolérancement de fabrication restreint aux procédés d'usinage. Mon activité de recherche peut donc se résumer par le développement d'une approche variationnelle de l'analyse des tolérances géométriques de systèmes de solides infiniment rigides et de systèmes dont les variations d'origine thermomécanique sont prises en comptes.Cette approche variationnelle m'a amené à considérer la problématique de structuration des données pour le tolérancement en se focalisant sur la traçabilité des spécifications d'un point de vue interniveaux et intervues. Enfin, le transfert de spécifications fonctionnelles d'une pièce élaborée par le procédé RTM a été considéré pour aborder la corrélation de spécifications fonctionnelles avec les spécifications inhérentes au procédé RTM.

Systematize is the leitmotiv of the results in this thesis. Three problems are studied in the field of computer vision and computational geometry. In the first one, we extend all the machinery of the pinhole model for classical cameras to a whole set of cameras (two-slit, pushbroom, oblique, pencil), which were separately studied with different approaches. In the second one, we generalize to convex bodies in R3 the work on pinning lines by or balls, which had so far been tackled by techniques intimately linked to the geometry of the objects. In the third one, we attempt to work out a systematic approach in place of problem-specific methods in order to build polynomial evaluation trees for geometric predicates.Such goals could not be reached without a mathematical investigation in the study of linear line congruences, differential properties of sets of tangent lines to a convex and classical invariant theory respectively. These tools or their uses are mostly based on line geometry in P3 (R). This geometry was designed in the second half of the 19th century but its full power hos not yet been used by the computational geometry community. This thesis therefore also serves as an extended tutorial.; Systématiser : tel est le leitmotiv des résultats de cette thèse portant sur trois domaines d'étude en vision et en géométrie algorithmique. Dans le premier, nous étendons toute la machinerie du modèle sténopé des appareils photos classiques à un ensemble d'appareils photo (deux fentes, à balayage, oblique, une fente) jusqu'à présent étudiés séparément suivant différentes approches. Dans le deuxième, nous généralisons avec peu d'efforts aux convexes de R3 l'étude des épinglages de droites ou de boules, menée différemment selon la nature des objets considérés. Dans le troisième, nous tentons de dégager une approche systématique pour élaborer des stratégies d'évaluation polynomiale de prédicats géométriques, les méthodes actuelles étant bien souvent spécifiques à chaque prédicat étudié.De tels objectifs ne peuvent être atteints sans un certain investissement mathématique dans l'étude des congruences linéaires de droites, de propriétés différentielles des ensembles de tangentes à des convexes et de la théorie des invariants algébriques, respectivement. Ces outils ou leurs utilisations reposent sur la géométrie de P3 (R), construite dans la seconde moitié du XIXe siècle mais pas complètement assimilée en géométrie alogorithmique et dont nous proposons une synthèse adaptée aux besoins de la communauté.

Systematize is the leitmotiv of the results in this thesis. Three problems are studied in the field of computer vision and computational geometry. In the first one, we extend all the machinery of the pinhole model for classical cameras to a whole set of cameras (two-slit, pushbroom, oblique, pencil), which were separately studied with different approaches. In the second one, we generalize to convex bodies in R3 the work on pinning lines by or balls, which had so far been tackled by techniques intimately linked to the geometry of the objects. In the third one, we attempt to work out a systematic approach in place of problem-specific methods in order to build polynomial evaluation trees for geometric predicates.Such goals could not be reached without a mathematical investigation in the study of linear line congruences, differential properties of sets of tangent lines to a convex and classical invariant theory respectively. These tools or their uses are mostly based on line geometry in P3 (R). This geometry was designed in the second half of the 19th century but its full power hos not yet been used by the computational geometry community. This thesis therefore also serves as an extended tutorial., Systématiser : tel est le leitmotiv des résultats de cette thèse portant sur trois domaines d'étude en vision et en géométrie algorithmique. Dans le premier, nous étendons toute la machinerie du modèle sténopé des appareils photos classiques à un ensemble d'appareils photo (deux fentes, à balayage, oblique, une fente) jusqu'à présent étudiés séparément suivant différentes approches. Dans le deuxième, nous généralisons avec peu d'efforts aux convexes de R3 l'étude des épinglages de droites ou de boules, menée différemment selon la nature des objets considérés. Dans le troisième, nous tentons de dégager une approche systématique pour élaborer des stratégies d'évaluation polynomiale de prédicats géométriques, les méthodes actuelles étant bien souvent spécifiques à chaque prédicat étudié.De tels objectifs ne peuvent être atteints sans un certain investissement mathématique dans l'étude des congruences linéaires de droites, de propriétés différentielles des ensembles de tangentes à des convexes et de la théorie des invariants algébriques, respectivement. Ces outils ou leurs utilisations reposent sur la géométrie de P3 (R), construite dans la seconde moitié du XIXe siècle mais pas complètement assimilée en géométrie alogorithmique et dont nous proposons une synthèse adaptée aux besoins de la communauté.

We tackle in this thesis the problem of computing the topology of plane algebraic curves. We present an algorithm that avoids special treatment of degenerate cases, based on algebraic tools such as Gröbner bases and rational univariate representations. We implemented this algorithm and showed its performance by comparing to similar existing programs. We also present an output-sensitive complexity analysis of this algorithm. We then discuss the tools that are necessary for the implementation of non-linear geometric algorithms in CGAL, the reference library in the computational geometry community. We present an univariate algebraic kernel for CGAL, a set of functions aimed to handle curved objects defined by univariate polynomials. We validated our approach by comparing it to other similar implementations.; Nous abordons dans cette thèse le problème du calcul de la topologie de courbes algébriques planes. Nous présentons un algorithme qui, grâce à l'application d'outils algébriques comme les bases de Gröbner et les représentations rationnelles univariées, ne nécessite pas de traitement particulier de cas dégénérés. Nous avons implanté cet algorithme et démontré son efficacité par un ensemble de comparaisons avec les logiciels similaires. Nous présentons également une analyse de complexité sensible a la sortie de cet algorithme. Nous discutons ensuite des outils nécessaires pour l'implantation d'algorithmes de géométrie non-linéaire dans CGAL, la bibliothèque de référence de la communauté de géométrie algorithmique. Nous présentons un noyau univarié pour CGAL, un ensemble de fonctions nécessaires pour le traitement d'objets courbes définis par des polynômes univariés. Nous avons validé notre approche en la comparant avec les implantations similaires.

The objective of this thesis is to investigate the problem of boundary evaluation for scenes defined by quadrics. This algorithm consists of four steps : (i) the parameterization of every intersection curve between quadrics ; (ii) the calculation of the intersection points between such curves and the quadrics ; (iii) the determination, among the resulting arcs of curves of those that limit a face of the BRep model; (iv) the identification of the arcs that delimit a singe face, and their assembling into chains of arcs ; some faces might contain <>, and thus may be limited by several chains of arcs. The first two steps were solved using two algorithms from the litterature. The two remaining steps were solved by introducing new algorithms : VE (Visible Edges) and CA (Chains Assembling) respectively. Our algorithm of boundary evaluation is robust in the sense that all degenerate configurations are considered in the paradigm of exact geometric computing. Il solves entirely the problem for scenes defined by quadrics. Its time-complexity id $O(n^4)$ in the worst case, where $n$ is the number of quadrics. A partial implementation was developed and preliminary experimental results were obtained.; L'objet de cette thèse porte sur la conversion d'un modèle CSG vers un modèle BRep d'une scène définie par des quadriques. Cet algorithme est composé de quatre étapes : (i) le paramétrage de chaque courbe d'intersection entre quadriques ; (ii) la détermination des points d'intersection entre au moins trois quadriques ; (iii) la détection des segments ainsi obtenus qui bornent une face du modèle BRep sur chacune des quadriques séparément ; (iv) l'identification et le regroupement des chaînes de segments qui délimitent une même face sur chaque quadrique séparément (certaines faces peuvent avoir des <>, et par conséquent être constituées par au moins deux chaînes de segments). Les deux premières étapes ont été résolues grâce à deux algorithmes de la littérature. Les deux étapes restantes sont traitées par des algorithmes que nous avons conçus : respectivement VE (Visible Edges) et CA (Chains Assembling). Notre algorithme est robuste au sens où tous les cas dégénérés sont traités dans le paradigme du calcul géométrique exact. Il résout intégralement le problème de conversion CSG-BRep de scènes définies par des quadriques. Sa complexité dans le pire des cas s'élève à $O(n^4)$ où $n$ est le nombre de quadriques. Une implantation partielle a été effectuée et des tests préliminaires réalisés.

The objective of this thesis is to investigate the problem of boundary evaluation for scenes defined by quadrics. This algorithm consists of four steps : (i) the parameterization of every intersection curve between quadrics ; (ii) the calculation of the intersection points between such curves and the quadrics ; (iii) the determination, among the resulting arcs of curves of those that limit a face of the BRep model; (iv) the identification of the arcs that delimit a singe face, and their assembling into chains of arcs ; some faces might contain <>, and thus may be limited by several chains of arcs. The first two steps were solved using two algorithms from the litterature. The two remaining steps were solved by introducing new algorithms : VE (Visible Edges) and CA (Chains Assembling) respectively. Our algorithm of boundary evaluation is robust in the sense that all degenerate configurations are considered in the paradigm of exact geometric computing. Il solves entirely the problem for scenes defined by quadrics. Its time-complexity id $O(n^4)$ in the worst case, where $n$ is the number of quadrics. A partial implementation was developed and preliminary experimental results were obtained.; L'objet de cette thèse porte sur la conversion d'un modèle CSG vers un modèle BRep d'une scène définie par des quadriques. Cet algorithme est composé de quatre étapes : (i) le paramétrage de chaque courbe d'intersection entre quadriques ; (ii) la détermination des points d'intersection entre au moins trois quadriques ; (iii) la détection des segments ainsi obtenus qui bornent une face du modèle BRep sur chacune des quadriques séparément ; (iv) l'identification et le regroupement des chaînes de segments qui délimitent une même face sur chaque quadrique séparément (certaines faces peuvent avoir des <>, et par conséquent être constituées par au moins deux chaînes de segments). Les deux premières étapes ont été résolues grâce à deux algorithmes de la littérature. Les deux étapes restantes sont traitées par des algorithmes que nous avons conçus : respectivement VE (Visible Edges) et CA (Chains Assembling). Notre algorithme est robuste au sens où tous les cas dégénérés sont traités dans le paradigme du calcul géométrique exact. Il résout intégralement le problème de conversion CSG-BRep de scènes définies par des quadriques. Sa complexité dans le pire des cas s'élève à $O(n^4)$ où $n$ est le nombre de quadriques. Une implantation partielle a été effectuée et des tests préliminaires réalisés.

International audience; We present a new optimization technique that yields the first FPTAS for several geometric problems These problems reduce to optimizing a sum of non-negative, constant description-complexity algebraic functions We first give a FPTAS for optimizing such a sum of algebraic functions, and then we apply it, to several geometric optimization problems We obtain the first, FPTAS for two fundamental geometric shape matching problems in fixed dimension: maximizing the volume of over lap of two polyhedra uncle, rigid motions, and minimizing their symmetric difference We obtain the first FPTAS for other problems in fixed dimension, such as computing an optimal ray in a weighted subdivision, finding the largest axially symmetric subset of a. polyhedron, and computing minimum area hulls.

The purpose of this doctoral thesis is to provide a method to reconstruct three dimensional shapes from cross-sections. The principal motivation is 3D reconstruction of organs that is widely considered to be an important diagnostic aid in the medical world. However, the actual simulation results, namely in 3D ultrasonic simulation, are not reliable to be used in diagnosis. This thesis is the first geometric analysis of the reliability and the validity of reconstruction methods from cross-sectional data. Even in the case of parallel sections, no formal analysis and guarantees had been obtained before this thesis. More formally, we consider the problem of reconstructing a compact 3-manifold (with boundary) embedded in R3 from its cross-sections with a given set of cutting planes having arbitrary orientations. The first Chapter of this manuscript is devoted to analyzing a method presented by Liu et al. in 2008. We prove that under appropriate sampling conditions, the resulting reconstructed object is homeomorphic (and isotopic) to the original object. In the second chapter, we present a second reconstruction method that makes use of the Voronoi diagram of the sections. This method performs more connections between the sections comparing to the first method. Increasing the connectivity between the sections is motivated by reconstructing tree-like structures from sparse sectional data. The provided sampling conditions, leading to topological guarantees, are adapted to tree-like structures: Indeed, we show that if the cutting planes are sufficiently transversal to the surface we want to reconstruct, then the method can handle complex branching structures. Finally, in the third chapter, we show how the Voronoi-Delaunay duality allows us to perform still more connections between the sections comparing to the two first methods. The preliminary experimental results are quite promising, e.g., regarding the practicality of the approach to reconstruct complex cross-sectional branching situations such as the coronary arterial tree. The hope is that the theoretical studies provided in this thesis will be a first step to provide solid foundations and theoretical guarantees for medical diagnostic software., Le sujet de cette thèse porte sur la reconstruction de formes à partir de coupes planaires. Dans de nombreux domaines d'application, il est nécessaire de reconstruire des formes à partir de sections. L'importance du sujet en imagerie médicale a conduit, depuis les années 1990, à des résultats importants qui sont cependant pour la plupart limités au cas de sections parallèles. Pourtant en échographie, les données obtenues au moyen d'une sonde guidée manuellement, forment une série d'images représentant des coupes de l'organe par des plans non parallèles. Cette application directe motivait le sujet de ma thèse. Dans cette thèse nous considérons le problème de la reconstruction d'une 3-variété à bord plongée dans R^3, à partir de ses intersections avec un ensemble de plans en positions arbitraires, appelées coupes. C'est pour la première fois que ce problème est étudié en toute généralité, dans le but de fournir des garanties théoriques satisfaisantes sur le résultat de la reconstruction. Aucune garantie théorique n'a été obtenue même pour le cas de coupes parallèles avant cette thèse. Dans le premier chapitre de ce manuscrit, nous étudions la méthode de reconstruction proposée par Liu et al. en 2008. Nous prouvons que si certaines conditions d'échantillonnage sont vérifiées, cette méthode permet de reconstruire la topologie de l'objet à partir des coupes données. Nous prouvons également que l'objet reconstruit est homéomorphe (et isotope) à l'objet. Le deuxième chapitre présente une nouvelle méthode de reconstruction en utilisant le diagramme de Voronoi des sections. Cette méthode permet d'établir plus de connections entre les sections par rapport à la première méthode. Favoriser les connections entre les sections est motivé par la reconstruction d'objets fins à partir de sections peu denses. Nous présentons des conditions d'échantillonnage qui sont adaptées aux objets fins et qui permettent de prouver l'équivalence homotopique entre l'objet reconstruit et l'objet de départ. En effet, nous prouvons que si les plans de coupe sont suffisamment transversales à l'objet, notre méthode de reconstruction est topologiquement valide et peut traiter des topologies complexes des sections avec plusieurs branchements. Dans le dernier chapitre de ce manuscrit, nous présentons une autre méthode de reconstruction qui permet d'établir encore plus de connections entre les sections en comparant avec les deux premières méthodes. Notre méthode est basée sur la triangulation de Delaunay et suit une approche duale en considérant le diagramme de Voronoi des sections. L'algorithme correspondant a été implémenté en C++, en utilisant la bibliothèque CGAL. Les résultats de la reconstruction obtenus par cet algorithme sont très satisfaisants pour les topologies complexes des sections. En se basant sur les études que nous avons développées durant cette thèse, nous espérons pouvoir fournir un fondement solide pour le processus d'acquisition et de reconstruction des données échographiques afin d'avoir un logiciel fiable pour les diagnostics.

In computer science, pictures are digital and so, they are composed of pixels in 2D or of voxels in 3D. In 3D virtual scenes, we cannot directly manipulate objects as sets of voxels because the data are too huge. As a result, the objects are transformed into polyhedra, i.e. collections of facets. For this, we must be able to decide if a subset of voxels can be replaced by a facet in the polyhedrisation. This problem is called digital plane recognition. To solve it, we design a new algorithm especially adapted for sets of voxels which are dense in a bounding box. Our method achieves a quasi-linear worst-case time complexity in this case and it is efficient in practice. In parallel, we study another algorithmic problem which occures in our digital plane recognition algorithm. It is computing the two convex hulls of grid points lying in a bounded vertical domain and located on either side of a straight line. We propose an optimal time complexity method to compute these convex hulls and which is also output sensitive. We present the problem in a different way : find the rational number of bounded denominator that best approximates a given real number. We establish the link between this numerical problem and geometry. Finally, we independently propose a new algorithm to compute the lattice width of a set of points in Zd. Our method is optimal in 2D and is greedy but efficent in higher dimension, En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c’est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s’avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s’agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d’autre d’une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l’épaisseur d’un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure

International audience; In this paper a framework for defining scale-spaces, based on the computational geometry concepts of α-shapes, is proposed. In this approach, objects (curves or surfaces) of increasing convexity are com- puted by selective sub-sampling, from the original shape to its convex hull. The relationships with the Empirical Mode Decomposition (EMD), the curvature motion-based scale-space and some operators from math- ematical morphology, are studied. Finally, we address the problem of additive image/signal decomposition in fluorescence video-microscopy. An image sequence is mainly considered as a collection of 1D temporal signals, each pixel being associated with its temporal intensity variation.

In this thesis, we define a static analysis by abstract interpretation of memory manipulations. It is based on a new numerical abstract domain, which is able to infer program invariants involving the operators min and max. This domain relies on tropical polyhedra, which are the analogues of convex polyhedra in tropical algebra. Tropical algebra refers to the set IR U {-oo} endowed with max as addition and + as multiplication. This abstract domain is provided with sound abstract primitives, which allow to automatically compute over-approximations of semantics of programs by means of tropical polyhedra. Thanks to them, we develop and implement a sound static analysis inferring min- and max-invariants over the program variables, the length of the strings, and the size of the arrays in memory. In order to improve the scalability of the abstract domain, we also study the algorithmics of tropical polyhedra. In particular, a tropical polyhedron can be represented in two different ways, either internally, in terms of extreme points and rays, or externally, in terms of tropically affine inequalities. Passing from the external description of a polyhedron to its internal description, or inversely, is a fundamental computational issue, comparable to the well-known vertex/facet enumeration or convex hull problems in the classical algebra. It is also a crucial operation in our numerical abstract domain. For this reason, we develop two original algorithms allowing to pass from an external description of tropical polyhedra to an internal description, and vice versa. They are based on a tropical analogue of the double description method introduced by Motzkin et al. We show that they outperform the other existing methods, both in theory and in practice. The cornerstone of these algorithms is a new combinatorial characterization of extreme elements in tropical polyhedra defined by means of inequalities: we have proved that the extremality of an element amounts to the existence of a strongly connected component reachable from any node in a directed hypergraph. We also show that the latter property can be checked in almost linear time in the size of the hypergraph. Moreover, in order to have a better understanding of the intrinsic complexity of tropical polyhedra, we study the problem of determining the maximal number of extreme points in a tropical polyhedron. In the classical case, this problem is addressed by McMullen upper bound theorem. We prove that the maximal number of extreme points in the tropical case is bounded by a similar result. We introduce a class of tropical polyhedra appearing as natural candidates to be maximizing instances. We establish lower and upper bounds on their number of extreme points, and show that the McMullen type bound is asymptotically tight when the dimension tends to infinity and the number of inequalities defining the polyhedra is fixed. Finally, we experiment our tropical polyhedra based static analyzer on programs manipulating strings and arrays. These experimentations show that the analyzer successfully determines precise properties on memory manipulations, and that it scales up to highly disjunctive invariants which could not be computed by the existing methods. The implementation of all the algorithms and abstract domains on tropical polyhedra developed in this work is available in the Tropical Polyhedra Library (TPLib).

National audience; Surfaces, c’est le thème proposé aux étudiants des classes préparatoires aux grandes écoles pour leurs TIPE de l’année 2009-2010. Une occasion pour nous de plancher sur ce sujet.

The work presented in this thesis concerns the fields of image analysis and discrete geometry. Image analysis aims at automatically describing the visual content of a digital image and discrete geometry provides tools devoted to digital image processing. A two-dimensional analog signal is regularly sampled in order to be handled on computers. This acquisition process results in a digital image, which is made up of a finite set of discrete elements. The topic of discrete geometry is to study the geometric properties of such kind of discrete spaces. In this work, we consider homogeneous regions of an image having a meaning for a user. The objective is to represent their digital contour by means of geometric patterns and compute measures. The scope of applications is wide in image analysis. For instance, our results would be of great interest for segmentation or object recognition. We focus on three discrete geometric patterns defined by Gauss digitization: the convex or concave part, the digital straight segment and the digital circular arc. We present several algorithms that detect or recognize these patterns on a digital contour. These algorithms are on-line, exact (integer-only computations without any approximation error) and fast (simplified computations thanks to arithmetic properties and linear-time complexity). They provide a way for segmenting a digital contour or for representing a digital contour by a reversible polygon. Moreover, we define a measure of convexity, a measure of straightness and a measure of circularity. These measures fulfil the following important properties: they are robust to rigid transformations, they may be applied on any part of a digital contour, they reach their maximal value for the template with which the data are compared to. From these measures, we introduce new patterns having a parameter that ranges from 0 to 1. The parameter is set to 1 when the localisation of the digital contour is reliable, but is set to a lower value when the digital contour is expected to have been shifted because of some acquisition noise. This measure-based approach provides a way for robustly decomposing a digital contour into convex, concave or straight parts., Cette thèse se situe à l'interface entre l'analyse d'images, dont l'objectif est la description automatique du contenu visuel, et la géométrie discrète, qui est l'un des domaines dédiés au traitement des images numériques. Pour être stocké et manipulé sur un ordinateur, un signal observé est régulièrement échantillonné. L'image numérique, qui est le résultat de ce processus d'acquisition, est donc constituée d'un ensemble fini d'éléments distincts. La géométrie discrète se propose d'étudier les propriétés géométriques d'un tel espace dépourvu de continuité. Dans ce cadre, nous avons considéré les régions homogènes et porteuses de sens d'une image, avec l'objectif de représenter leur contour au moyen de modèles géométriques ou de les décrire à l'aide de mesures. L'étendue des applications de ce travail en analyse d'images est vaste, que ce soit au cours du processus de segmentation, ou en vue de la reconnaissance d'un objet. Nous nous sommes concentrés sur trois modèles géométriques discrets définis par la discrétisation de Gauss : la partie convexe ou concave, l'arc de cercle discret et le segment de droite discrète. Nous avons élaboré des algorithmes dynamiques (mise à jour à la volée de la décision et du paramétrage), exacts (calculs en nombres entiers sans erreur d'approximation) et rapides (calculs simplifiés par l'exploitation de propriétés arithmétiques et complexité en temps linéaire) qui détectent ces modèles sur un contour. L'exécution de ces algorithmes le long d'un contour aboutit à des décompositions ou à des polygonalisations réversibles. De plus, nous avons défini des mesures de convexité, linéarité et circularité, qui vérifient un ensemble de propriétés fondamentales : elles sont robustes aux transformations rigides, elles s'appliquent à des parties de contour et leur valeur maximale est atteinte pour le modèle de forme qui sert de comparaison et uniquement sur celui-ci. Ces mesures servent à l'introduction de nouveaux modèles dotés d'un paramètre variant entre 0 et 1. Le paramètre est fixé à 1 quand on est sûr de la position du contour, mais fixé à une valeur inférieure quand le contour est susceptible d'avoir été déplacé par un bruit d'acquisition. Cette approche pragmatique permet de décomposer de manière robuste un contour en segments de droite ou en parties convexes et concaves.

To compute shadows in computer graphics, it is common to be interested in the view of a geometric scene by an observer. Particularly, it is important to characterize the structural changes, called visual events, taking place in the view when the observer moves. Based on the combinatorial definition of view introduced by Gigus and Malik and the associated classification of visual events, many studies suffer from time and space complexity problems. For example, it is the case of discontinuity meshing. Thus, we suggest a new approach which relies on a questionning about this notion of view. For a set of pairwise disjoint convex objects, we propose a topological definition of view emphasizing the visible silhouettes of objects in the scene and we geometrically characterize the locus where those visual events take place. We use this characterization to propose a method to extract boundaries between full light and penumbra and between penumbra and umbra in a scene lit by area light sources. We manage to strongly reduce the size of intermediate objects in use to build the limits between those regions.Furthermore, we prove the first non trivial theoretical bounds on the complexity of the limits between full-light and penumbra and between penumbra and umbra.; Pour le calcul d'ombres en informatique graphique, il est courant de s'intéresser à la vue qu'un observateur a d'une scène géométrique. En particulier, il est important de caractériser les changements structurels, appelés événements visuels, qui se produisent dans cette vue lorsque l'observateur se déplace. En se basant sur la définition combinatoire de la vue proposée par Gigus et Malik et la classification des événements visuels qui en découle, de nombreux travaux se heurtent à des problèmes de complexité en temps et en espace. C'est notamment le cas de la méthode du maillage de discontinuités. Nous suggérons donc une approche nouvelle qui repose sur la remise en cause de cette notion de vue.Pour un ensemble d'objets convexes disjoints, nous proposons une définition topologique de la vue qui fait la part belle aux silhouettes visibles des objets de la scène et nous caractérisons géométriquement les lieux où se produisent les événements visuels. Nous utilisons cette caractérisation pour proposer une méthode qui permet d'extraire les limites entre lumière et pénombre et entre ombre et pénombre dans une scène éclairée par des sources surfaciques. Nous arrivons ainsi à réduire considérablement la taille des objets intermédiaires utilisés pour la construction des limites entre les régions.De plus, nous démontrons les premières bornes théoriques non triviales sur la complexité des limites entre lumière et pénombre ainsi qu'entre ombre et pénombre.

To compute shadows in computer graphics, it is common to be interested in the view of a geometric scene by an observer. Particularly, it is important to characterize the structural changes, called visual events, taking place in the view when the observer moves. Based on the combinatorial definition of view introduced by Gigus and Malik and the associated classification of visual events, many studies suffer from time and space complexity problems. For example, it is the case of discontinuity meshing. Thus, we suggest a new approach which relies on a questionning about this notion of view. For a set of pairwise disjoint convex objects, we propose a topological definition of view emphasizing the visible silhouettes of objects in the scene and we geometrically characterize the locus where those visual events take place. We use this characterization to propose a method to extract boundaries between full light and penumbra and between penumbra and umbra in a scene lit by area light sources. We manage to strongly reduce the size of intermediate objects in use to build the limits between those regions.Furthermore, we prove the first non trivial theoretical bounds on the complexity of the limits between full-light and penumbra and between penumbra and umbra.; Pour le calcul d'ombres en informatique graphique, il est courant de s'intéresser à la vue qu'un observateur a d'une scène géométrique. En particulier, il est important de caractériser les changements structurels, appelés événements visuels, qui se produisent dans cette vue lorsque l'observateur se déplace. En se basant sur la définition combinatoire de la vue proposée par Gigus et Malik et la classification des événements visuels qui en découle, de nombreux travaux se heurtent à des problèmes de complexité en temps et en espace. C'est notamment le cas de la méthode du maillage de discontinuités. Nous suggérons donc une approche nouvelle qui repose sur la remise en cause de cette notion de vue.Pour un ensemble d'objets convexes disjoints, nous proposons une définition topologique de la vue qui fait la part belle aux silhouettes visibles des objets de la scène et nous caractérisons géométriquement les lieux où se produisent les événements visuels. Nous utilisons cette caractérisation pour proposer une méthode qui permet d'extraire les limites entre lumière et pénombre et entre ombre et pénombre dans une scène éclairée par des sources surfaciques. Nous arrivons ainsi à réduire considérablement la taille des objets intermédiaires utilisés pour la construction des limites entre les régions.De plus, nous démontrons les premières bornes théoriques non triviales sur la complexité des limites entre lumière et pénombre ainsi qu'entre ombre et pénombre.

We consider approximate nearest neighbor searching in metric spaces of constant doubling dimension. More formally, we are given a set Sof npoints and an error bound i¾?> 0. The objective is to build a data structure so that given any query point qin the space, it is possible to efficiently determine a point of Swhose distance from qis within a factor of (1 + i¾?) of the distance between qand its nearest neighbor in S. In this paper we obtain the following space-time tradeoffs. Given a parameter i¾?i¾? [2,1/i¾?], we show how to construct a data structure of space $n \gamma^{O(\dim)} \log(1/\varepsilon)$ space that can answer queries in time $O(\log(n\gamma)) + (1/(\varepsilon \gamma))^{O(\dim)}$. This is the first result that offers space-time tradeoffs for approximate nearest neighbor queries in doubling spaces. At one extreme it nearly matches the best result currently known for doubling spaces, and at the other extreme it results in a data structure that can answer queries in time O(log(n/i¾?)), which matches the best query times in Euclidean space. Our approach involves a novel generalization of the AVD data structure from Euclidean space to doubling space.

Dynamic mesh adaptation on unstructured grids, by localised refinement and derefinement, is a very efficient tool for enhancing solution accuracy and optimise computational time. One of the major drawbacks however resides in the projection of the new nodes created, during the refinement process, onto the boundary surfaces. This can be addressed by the introduction of a library capable of handling geometric properties given by a CAD (Computer Aided Design) description. This is of particular interest also to enhance the adaptation module when the mesh is being smoothed, and hence moved, to then re-project it onto the surface of the exact geometry. However, the above procedure is not always possibly due to either faulty or too complex designs, which require a higher level of complexity in the CAD library. It is therefore paramount to have a built-in algorithm able to place the new nodes, belonging to the boundary, closer to the geometric definition of it. Such a procedure is proposed in this work, based on the idea of interpolating subdivision. In order to efficiently and effectively adapt a mesh to a solution field, the criteria used for the adaptation process needs to be as accurate as possible. Due to the nature of the solution, which is obtained by discretisation of a continuum model, numerical error is intrinsic in the calculation. A posteriori error estimation allows us to somewhat assess the accuracy by using the computed solution itself. In particular, an a posteriori error estimator based on the Zienkievicz Zhu model is introduced. This can be used in the adaptation procedure to refine the mesh in those areas where the local error exceeds a set tolerance, hence further increasing the accuracy of the solution in those regions during the next computational step. Variants of this error estimator have also been studied and implemented. One of the important aspects of this project is the fact that the algorithmic concepts are developed thinking parallel, i.e. the algorithms take into account the possibility of multiprocessor implementation. Indeed these concepts require complex programming if one tries to parallelise them, once they have been devised serially. Another important and innovative aspect of this work is the consistency of the algorithms with parallel processor execution.

Whereas the international community of computational geometry is oftentempted to plunge into essentially theoretical research, in particularof a combinatorial nature, the main originality of the work at INRIAresided, already when I started, in the concern of experimentalvalidation and applicability. The field globally evolved in this direction, in particular after the``Impact Task Force Report''. Our interest for technologic andindustrial transfer, and for setting up a platform for research,became even more concrete with our strong implication in the CGALproject for which our group is one of the leaders. This document choses to present the work from the point of view ofthis practical concern. It consists of two main chapters: the first one gatherswork on triangulations, the second presents work on curvedobjects. These two chapters are concluded by a set of opendirections. The third chapter quickly surveys other results.; Si la communauté internationale de géométrie algorithmique a souventla tentation de s'engouffrer dans des recherches essentiellementthéoriques, et en particulier combinatoires, la grande originalité destravaux à l'INRIA résidait déjà à l'époque de mes débuts dans lesouci de leur validation expérimentale et de leur applicabilité. Le domaine a suivi globalement une évolution dans cette direction,en particulier grâce à l'``Impact Task Force Report''. Notre intérêt pour le transfert technologique etindustriel, ainsi que pour l'établissement d'une plateforme pour larecherche, a pris pendant ce temps une tournure encore plus concrèteavec notre implication très forte dans le projet CGALdont notre équipe est l'un des moteurs.Ce document prend le parti de présenter les travaux sous l'angle decette préoccupation pratique.Il comporte deux chapitres principaux : le premier rassembledes travaux sur les triangulations, le second présente des travaux surles objets courbes. Ces deux chapitres se concluent par un ensemble dedirections ouvertes. Le troisième chapitre survole rapidement d'autresrésultats.

This Habilitation thesis presents my main work over the last years in non-linear computational geometry. I present two bodies of work, one on the design and implementation of certified and efficient geometric algorithms for non-linear primitives, in particular quadrics, the other on the properties of lines in space in the context of 3D visibility problems. Concerning quadrics, my main achievement has been the completion of the first-ever exact, complete, near-optimal and efficient algorithm and implementation for parameterizing the intersection of two quadrics in three-dimensional real projective space. This contribution is a considerable breakthrough on a long-standing open problem and it is the first complete and robust solution to one of the most basic problems of solid modeling by implicit curved surfaces. I also present some very nice results on Voronoi diagrams of three lines, a partition of the space in cells bounded by quadric patches. We show that the topology of such diagrams is invariant for lines in general position and we obtain a monotonicity property on the arcs of the diagram. We deduce a simple algorithm for sorting points along such an arc, which is presumably of great interest for future efficient algorithms for computing the medial axis of a polyhedron. The proof technique, which relies heavily upon modern tools of computer algebra, is also interesting in its own right.Concerning the properties of lines in space in the context of 3D visibility problems, I present a body of results that address several issues. I first present results on the structural properties of lines that are tangent or transversal to four primitives. In particular, I present a characterization of the degenerate configurations of four spheres that admit infinitely many common tangent, a characterization of the set of line transversals to four segments, and a study of the worst-case number of tangents to four triangles. Second, I present several results on the combinatorial properties of geometric structures in the context of 3D visibility. In particular, I present several important results on the complexity of the silhouette of a polyhedron from a random viewpoint and on the worst-case and expected complexity of the visibility complex, a data structure that encode visibility information. I also present some new surprising bounds on the worst-case complexity of the umbra cast on a plane by polygonal light sources in the presence of convex polyhedral obstacles. Finally, I present the first non-trivial implementable algorithm for computing the set of segments tangent to four among k possibly intersecting convex polyhedra, that is, roughly speaking, the vertices of the visibility complex.; Cette thèse présente un ensemble de travaux en géométrie algorithmique non linéaire portant d'unepart sur le développement d'algorithmes géométriques certifiés et efficaces traitant d'objets courbes et, en particulier, de quadriques et, d'autre part, sur les propriétés des droites de l'espace dans un contexte de visibilité tridimensionnelle.Ma réalisation principale concernant les quadriques est le développement du premier algorithme exacte, complet, quasi optimal et efficace pour calculer une paramétrisation de l'intersection de deux quadriques en trois dimensions. Cette contribution est une avancée très importante sur un problème ancien et c'est la première solution complète et certifiée à l'un des problèmes les plus élémentaires de modélisation par surfaces courbes implicites. Je présente également un très joli résultat sur les diagrammes de Voronoï de trois droites qui sont des partitions de l'espace en cellules bornées par des morceaux de quadriques. Nous montrons que la topologie de tels diagrammes est invariante pour des droites en positions générales et nous obtenons une propriété de monotonie sur les arcs des diagrammes. Nous en déduisons un algorithme simple pour ordonner des points le long de ces arcs, ce qui est vraisemblablement une avancée substantielle pour le développement futur d'algorithmes efficaces pour calculer l'axe médian de polyèdres. La technique de preuve, qui utilise fortement les outils modernes de calcul formel, est également intéressante en elle même.Concernant les propriétés des droites de l'espace dans un contexte de visibilité tridimensionnelle, je présente un ensemble de résultats cohérents sur différentes problématiques. En premier lieu, je présente des résultats sur les propriétés structurelles des droites tangentes ou transversales à quatre primitives. Précisément, je présente une caractérisation des configurations dégénérées de quatre sphères qui admettent un nombre infini de tangentes communes, une caractérisation de l'ensemble des droites transversales à quatre segments, et une étude du nombre maximum de tangentes à quatre triangles. Je présente ensuite plusieurs résultats sur les propriétés combinatoires de structures géométriques de visibilité tridimensionnelle. En particulier, je présente plusieurs résultats importants sur la complexité des silhouettes de polyèdres depuis un point de vu aléatoire et sur la complexité en moyenne et dans le cas le pire du complexe de visibilité, une structure de données encodant des informations de visibilité. Je présente également de nouvelles bornes étonnantes sur la complexité dans le cas le pire de l'ombre portée sur un plan par une source lumineuse polygonale en présence d'obstacles polyédriques convexes. En dernier lieu, je présente le premier algorithme non trivial et implantable pour calculer l'ensemble des segments tangents à quatre parmi $k$ polyèdres convexes non nécessairement disjoints, c'est-à-dire, essentiellement les sommets du complexe de visibilité.

This Habilitation thesis presents my main work over the last years in non-linear computational geometry. I present two bodies of work, one on the design and implementation of certified and efficient geometric algorithms for non-linear primitives, in particular quadrics, the other on the properties of lines in space in the context of 3D visibility problems. Concerning quadrics, my main achievement has been the completion of the first-ever exact, complete, near-optimal and efficient algorithm and implementation for parameterizing the intersection of two quadrics in three-dimensional real projective space. This contribution is a considerable breakthrough on a long-standing open problem and it is the first complete and robust solution to one of the most basic problems of solid modeling by implicit curved surfaces. I also present some very nice results on Voronoi diagrams of three lines, a partition of the space in cells bounded by quadric patches. We show that the topology of such diagrams is invariant for lines in general position and we obtain a monotonicity property on the arcs of the diagram. We deduce a simple algorithm for sorting points along such an arc, which is presumably of great interest for future efficient algorithms for computing the medial axis of a polyhedron. The proof technique, which relies heavily upon modern tools of computer algebra, is also interesting in its own right.Concerning the properties of lines in space in the context of 3D visibility problems, I present a body of results that address several issues. I first present results on the structural properties of lines that are tangent or transversal to four primitives. In particular, I present a characterization of the degenerate configurations of four spheres that admit infinitely many common tangent, a characterization of the set of line transversals to four segments, and a study of the worst-case number of tangents to four triangles. Second, I present several results on the combinatorial properties of geometric structures in the context of 3D visibility. In particular, I present several important results on the complexity of the silhouette of a polyhedron from a random viewpoint and on the worst-case and expected complexity of the visibility complex, a data structure that encode visibility information. I also present some new surprising bounds on the worst-case complexity of the umbra cast on a plane by polygonal light sources in the presence of convex polyhedral obstacles. Finally, I present the first non-trivial implementable algorithm for computing the set of segments tangent to four among k possibly intersecting convex polyhedra, that is, roughly speaking, the vertices of the visibility complex.; Cette thèse présente un ensemble de travaux en géométrie algorithmique non linéaire portant d'unepart sur le développement d'algorithmes géométriques certifiés et efficaces traitant d'objets courbes et, en particulier, de quadriques et, d'autre part, sur les propriétés des droites de l'espace dans un contexte de visibilité tridimensionnelle.Ma réalisation principale concernant les quadriques est le développement du premier algorithme exacte, complet, quasi optimal et efficace pour calculer une paramétrisation de l'intersection de deux quadriques en trois dimensions. Cette contribution est une avancée très importante sur un problème ancien et c'est la première solution complète et certifiée à l'un des problèmes les plus élémentaires de modélisation par surfaces courbes implicites. Je présente également un très joli résultat sur les diagrammes de Voronoï de trois droites qui sont des partitions de l'espace en cellules bornées par des morceaux de quadriques. Nous montrons que la topologie de tels diagrammes est invariante pour des droites en positions générales et nous obtenons une propriété de monotonie sur les arcs des diagrammes. Nous en déduisons un algorithme simple pour ordonner des points le long de ces arcs, ce qui est vraisemblablement une avancée substantielle pour le développement futur d'algorithmes efficaces pour calculer l'axe médian de polyèdres. La technique de preuve, qui utilise fortement les outils modernes de calcul formel, est également intéressante en elle même.Concernant les propriétés des droites de l'espace dans un contexte de visibilité tridimensionnelle, je présente un ensemble de résultats cohérents sur différentes problématiques. En premier lieu, je présente des résultats sur les propriétés structurelles des droites tangentes ou transversales à quatre primitives. Précisément, je présente une caractérisation des configurations dégénérées de quatre sphères qui admettent un nombre infini de tangentes communes, une caractérisation de l'ensemble des droites transversales à quatre segments, et une étude du nombre maximum de tangentes à quatre triangles. Je présente ensuite plusieurs résultats sur les propriétés combinatoires de structures géométriques de visibilité tridimensionnelle. En particulier, je présente plusieurs résultats importants sur la complexité des silhouettes de polyèdres depuis un point de vu aléatoire et sur la complexité en moyenne et dans le cas le pire du complexe de visibilité, une structure de données encodant des informations de visibilité. Je présente également de nouvelles bornes étonnantes sur la complexité dans le cas le pire de l'ombre portée sur un plan par une source lumineuse polygonale en présence d'obstacles polyédriques convexes. En dernier lieu, je présente le premier algorithme non trivial et implantable pour calculer l'ensemble des segments tangents à quatre parmi $k$ polyèdres convexes non nécessairement disjoints, c'est-à-dire, essentiellement les sommets du complexe de visibilité.

National audience; Bienvenue dans le jeu de Voronoï : affrontez l’ordinateur ou jouez entre amis, pour conquérir le plus vaste territoire. Amusez-vous bien !