Skip to Main content Skip to Navigation

Algorithmes géométriques adaptatifs

Frank Nielsen 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Document type :
Complete list of metadata

Cited literature [114 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Monday, June 10, 2013 - 4:35:31 PM
Last modification on : Saturday, January 27, 2018 - 1:30:51 AM
Long-term archiving on: : Wednesday, September 11, 2013 - 4:13:37 AM


  • HAL Id : tel-00832414, version 1



Frank Nielsen. Algorithmes géométriques adaptatifs. Géométrie algorithmique [cs.CG]. Université Nice Sophia Antipolis, 1996. Français. ⟨tel-00832414⟩



Record views


Files downloads