Algorithmes géométriques adaptatifs

This thesis deals with the design of algorithms in computational geometry whose complexity depends on the output-size, the so-called output-sensitive algorithms. We first describe the main paradigms that allow algorithms to be output-sensitive. Then, we give a near-optimal output-sensitive algorithm to compute the convex hull of general planar objects such that the output síze of the convex hull of any pair of objects is bounded. We extend the results to the case of envelopes and the partial decomposition of convex and maxima layers. Finally, we consider the problem for familles of convex objects which has been proven NP-hard. We first study the case of isothetic boxes and give an output-sensitive heuristic that is precision sensitive. Then,, We Consider the combinatorial properties of convex objects from the piercability point of view. We obtain a collection of algorithms for various class of objects, some of them implying Helly-type theorems.Les travaux effectués lors de cette thèse portent sur 1a construction d'algorithmes géométriques dit adaptatifs dans 1e sens ou leur temps de calcul s'adapte a la solution construite. Nous décrivons tout d'abord les principaux paradigmes qui permettent d'obtenir des algorithmes adaptatifs. Puis , nous proposons un algorithme quasi-optimal adaptatif pour le calcul d'enveloppe convexe d'objets planaires dont la complexité de l'enveloppe convexe de toute paire soit bornée. L'algorithme est basé sur une approche composite combinant 1e paradigme mariage avant conquête et 1a méthodologie du groupement en paquets. Nous considérons également le calcul de l'enveloppe supérieure de fonctions et la décomposition convexe partielle d'un ensemble de points. Finalement, nous nous sommes intéressés aux problèmes de perçabílíté d'objets qui ont été montré NP-difficiles. En premier lieu, nous avons étudié le cas de boîtes ísothétíques en donnant une heuristique adaptative dont 1a précision soit elle-même adaptative. Ensuite, nous avons étudié les propriétés combinatoires des objets convexes pour 1a perçabílíté. Nous obtenons une batterie d'algorithmes pour des classes variées d'objets dont certains prouvent l'exístence de théorèmes de type Helly