Efficient randomized algorithms for some geometric optimization problems


Journal Article

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 ℱ 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′ ∈ ℱ, 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 ℱ consists of O(n3+ε) 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 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(n3/2+ε), for any ε > 0. Our algorithm improves and simplifies previous solutions of all three problems.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Sharir, M

Published Date

  • January 1, 1996

Published In

Volume / Issue

  • 16 / 4

Start / End Page

  • 317 - 337

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/BF02712871

Citation Source

  • Scopus