Efficient randomized algorithms for some geometric optimization problems
Pankaj K. Agarwal, Micha Sharir · 1995
. In this paper we first prove the following combinatorial bound, concerning 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 functions f, f # # F , the surface f (x, y, z) = f # (x, y, z) is xy-monotone (actually, we need a somewhat weaker property). We show that the vertical decomposition of the minimization diagram of F consists of O(n 3+# ) cells (each of constant description complexity), for any #>0. In the second part of the paper, we present a general technique 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 enclosing a set of n points in the plane, and (iii) computing the "biggest stick" inside a simpl...