Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235584] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sharir, M, Efficient randomized algorithms for some geometric optimization problems, Discrete & Computational Geometry, vol. 16 no. 4 (1996), pp. 317-337, ISSN 0179-5376
    (last updated on 2017/12/18)

    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 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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320