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.