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.
