EFFICIENT RANDOMIZED ALGORITHMS FOR SOME GEOMETRIC OPTIMIZATION PROBLEMS

In this paper we first prove the following combinatorial bound, concer ning the complexity of the vertical decomposition of the minimization diagram of trivariate functions: Let F be a collection of n totally or partially defined algebraic trivariate functions of constant maximum degree, with the additional property that, for a given pair of functio ns f, f' epsilon F, the surface f(x, y, z) = f'(x: y, z) is xy-monoton e (actually, we need a somewhat weaker property). We show that the ver tical decomposition of the minimization diagram of F consists of O (n( 3+epsilon)) cells (each of constant description complexity), for any e psilon > 0. In the second part of the paper, we present a general tech nique that yields faster randomized algorithms for solving a number of geometric optimization problems, including (i) computing the width of a point set in 3-space, (ii) computing the minimum-width annulus encl osing a set of n points in the plane, and (iii) computing the ''bigges t stick'' inside a simple polygon in the plane. Using the above result on vertical decompositions, we show that the expected running time of all three algorithms is O (n(3/2+epsilon)), for epsilon > 0. Our algo rithm improves and simplifies previous solutions of all three problems .