Efficient Randomized Algorithms for Some Geometric Optimization
K P 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'' \in F$, the surface $f(x,y,z)=f''(x,y,z)$ is $xy$-monotone (actually, we need a somewhat weaker property---see below). We show that the vertical decomposition of the minimization diagram of $F$ consists of $O(n^{3+\varepsilon})$ cells (each of constant complexity), for any $\varepsilon < 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 simple polygon in the plane. the expected running time of all three algorithms is $O(n^{3/2+\varepsilon})$, for any $\varepsilon<0$. Our algorithm improves and simplifies previous solutions of all three problems.