|
|
Discrete Mathematics and Optimization Seminar
|
Mar. 2nd, 2009
|
Adaptive (Analysis of) Algorithms for Convex Hulls and Related Problems
Jérémy Barbay
Universidad de Chile
|
|
Adaptive analysis is a well known technique in computational geometry,
which refines the traditional worst case analysis over all instances of
fixed input size by taking into account some other parameters, such as
the size of the output in the case of output sensitive analysis. We
present two adaptive techniques for the computation of the convex hull in
two and three dimensions and of related problems. The first analysis
technique is based on the *input order* and yields results on the
computation of convex hulls in two and three dimensions, and the first
adaptive algorithms for Voronoi and Delaunay diagrams, through the
entropy of a partition of the input in easier instances. The second
analysis technique is based on the *structural entropy* of the instance,
and yields results on the computational complexity of planar convex hull
and of multiset sorting, through a generalization of output sensitivity
and a more precise analysis of the complexity of Kirkpatrick and Seidel's
algorithm. Our approach yields adaptive algorithms which perform faster
on many classes of instances, while performing asymptotically no worse in
the worst case over all instances of fixed size.
|
|
|
|