Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots.<br /><br />Les algorithmes randomisés ont été un des sujets ``chauds'' de ces dernières années et nous proposons ici des travaux ayant trait à des algorithmes dynamiques ou semi-dynamiques : tout d'abord un schéma général d'algorithmes semi-dynamiques avec des applications aux diagrammes de Voronoï, aux diagrammes de Voronoï d'ordre k aux arrangements, et ensuite deux algorithmes dynamiques (permettant d'insérer et de supprimer des données) pour la triangulation de Delaunay et le calcul d'un arrangement de segments. D'autres résultats concernent des algorithmes statiques, notamment le calcul du squelette d'un polygone simple en temps O(n log* n).<br /><br />La deuxième partie explore différentes modélisations des sphères. On peut en déduire notamment un algorithme en O(tk log n) pour la triangulation de Delaunay de n points appartenant à k plans en 3 dimensions, si t désigne la taille du résultat; dans la cas de deux plans cet algorithme atteint une complexité optimale de O(t+n log n). Nous proposons également un algorithme de complexité O(n^ ceil(d/2) +n log n) pour le calcul de l'enveloppe convexe de n sphères en dimension d, et un algorithme optimal (quadratique) pour le calcul de la surface de Connolly.<br /><br />La dernière partie traite de problèmes spécifiques à la planification de trajectoires, un premier chapitre concerne le cas de plusieurs robots polygonaux en translation dans le plan: certaines configurations appellées double-contacts peuvent jouer un rôle particulier dans certains cas. Ensuite deux résultats à propos de robots à pattes : l'analyse d'un cas simple que nous avons baptisé robot araignée, et l'étude de la stabilité d'un robot un peu plus complexe.

La modélisation des objets géométriques est incontournable dans de nombreuses disciplines et applications. L'évolution des moyens l'acquisition et de stockage a produit une hausse énorme des volumes utilisés pour stocker ces objets. La réduction des tailles de ces volumes fait l'objet de plusieurs domaines de recherches ; comme la compression, qui vise à compresser le volume au maximum, et l'élaboration de structures théoriques compactes qui minimisent la taille nécessaire à la représentation. Le but de cette thèse est de concevoir, et d'évaluer des solutions pratiques et exploitables pour représenter de<br />façon compacte les triangulations. Pour ce faire, deux issues sont explorées : modifier la représentation interne en mémoire des objets géométriques, et redéfinir les types abstraits des objets géométriques correspondants. Une première solution consiste à utiliser des indices sur une taille arbitraire de bits, au lieu des références absolues. Les gains dépendent de la taille de la triangulation, et aussi de la taille du mot mémoire de la machine. Le handicap majeur est le coût élevé de la méthode en termes de temps d'exécution. Une deuxième piste consiste à utiliser des catalogues stables. L'idée consiste à regrouper les triangles dans des micro-triangulations, et de représenter la triangulation comme un ensemble de ces micro-triangulations. Le nombre des références multiples vers les sommets, et des références réciproques entre voisins est alors nettement réduit. Les résultats sont <br />prometteurs, sachant que le temps d'exécution n'est pas dramatiquement altéré par la modification des méthodes d'accés aux triangles. Une troisième solution consiste à décomposer la triangulation en plusieurs sous-triangulations permettant ainsi de coder les références dans une sous-triangulation sur un nombre réduit de bits par rapport aux références absolues. Les résultats de cette techniques sont encourageants, et peuvent être amplifiés par d'autres techniques comme le codage relatif des références, ou le partage de l'information géométrique des sommets sur les bords entre les différentes sous-triangulations. L'élaboration de structures compactes nécessite encore plus d'intérêts, et plusieurs pistes sont à explorer pour pouvoir arriver à des solutions plus économiques en termes d'espace mémoire.

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.

Cette thèse présente un ensemble de travaux en géométrie algorithmique non linéaire portant d'une<br />part 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.<br /><br />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.<br /><br />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é.

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 / 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

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 / 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

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}) / 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})

In this thesis, we focus on "structural information" in computer graphics, that is the information concerning the structure of 3D objects or scenes. More specifically, we define structural information as a two-scale notion, namely the object and the scene levels and propose a way of structuring 3D Geometry at both levels using the information of symmetry and instancing. In the first part of this thesis, we propose an original method to structure the geometry at the object level based on the information of symmetry. Inspired by the work on principal component analysis, we introduce for this purpose the generalized moment functions of a 3D shape. From the symmetry information that we have computed on the objects of the scene, we present in the second part of this thesis an approach to represent an unstructured 3D scene as a hierarchy of instances adapted to common tasks such as rendering or geometry editing.

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.<br /><br />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.<br /><br />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.

Dans la fabrication des produits pétroliers en raffinerie, les lois linéaires de mélange permettent de représenter les ensembles de mélanges faisables par des zonotopes. La faisabilité d'un mélange est un probleme important qui est résolu par des méthodes d'optimisation convexe. Le but du travail présente est de montrer que, dans le cas de la dimension trois, la géométrie algorithmique apporte d'autres solutions a ce probleme. La spécificité des zonoedres et l'utilisation d'une structure de données de type arête-ailée permettent la mise en œuvre d'algorithmes de géométrie optimaux pour les représenter, puis des algorithmes de manipulation et visualisation rapides et robustes destines a être utilises de manière concrète. Le logiciel développe a partir de ces outils apporte une aide efficace dans la décision de la fabrication des gazoles. Dans le cadre plus vaste de la séparation, l'état de séparation d'un système physico-chimique est représente par un zonoide. Les Zonodres fournissent une approche géométrique pour l'étude de tels objets