Math @ Duke

Publications [#235584] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M, Efficient randomized algorithms for some geometric optimization problems,
Discrete & Computational Geometry, vol. 16 no. 4
(1996),
pp. 317337, ISSN 01795376
(last updated on 2018/03/22)
Abstract: 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 xymonotone (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 3space, (ii) computing the minimumwidth 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

