Back to my home page.
Adaptive computational geometry (french: "Algorithmes géométriques adaptatifs")
Frank Nielsen
(Drawing is courtesy of Bernhard Geiger)
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-size 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 maximal layers. Finally, we consider the pierceability problem for families 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 pierceability point of view. We obtain a collection
of algorithms for various class of objects, some of them implying Helly-type theorems.
Download the PDF thesis (1523 KB, 254 pages)
Bibtex entry:
@PhDThesis{n-aga-1996,
author = "Frank Nielsen",
title = "Algorithmes g{\'e}om{\'e}triques adaptatifs",
type = "Th\`{e}se de doctorat en sciences",
school = "Universit\'e de {Nice-Sophia Antipolis}",
address = "France",
year = 1996,
url = "http://www.inria.fr/rrrt/tu-0418.html",
number = "TU-0418"
}
Related publications:
Frank Nielsen,
Adaptive Computational Geometry (Algorithmes géométriques adaptatifs)
Doctoral Thesis (Ph. D.)
University of Nice Sophia-Antipolis, FRANCE,
ISBN 2-7261-1017-7, 1996.
© Copyright notice.
Last updated, 2003.