Skip to Main content Skip to Navigation
Theses

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 :
Theses
Complete list of metadatas

Cited literature [114 references]  Display  Hide  Download

https://tel.archives-ouvertes.fr/tel-00832414
Contributor : Olivier Devillers <>
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

Identifiers

  • HAL Id : tel-00832414, version 1

Collections

Citation

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

Share

Metrics

Record views

1558

Files downloads

1738