# Efficient randomized algorithms for some geometric optimization problems

Published

Conference Paper

© 1995 ACM. 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 x,y-monotone (actually, we need a somewhat weaker property-see below). We show that the vertical decomposition of the minimization diagram of T consists of 0(n3+ϵ) cells (each of constant complexity), for any e > 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 0(n3/,2+ϵ), for any ϵ ≥ 0.

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Sharir, M

### Published Date

- September 1, 1995

### Published In

- Proceedings of the Annual Symposium on Computational Geometry

### Volume / Issue

- Part F129372 /

### Start / End Page

- 326 - 335

### International Standard Book Number 10 (ISBN-10)

- 0897917243

### Digital Object Identifier (DOI)

- 10.1145/220279.220314

### Citation Source

- Scopus