MAINTENANCE OF GEOMETRIC EXTREMA

Let S be a set, f: S x S --> R+ a bivariate function, and f(x, S) the maximum value of f(x, y) over all elements y is-an-element-of S. We say that f is decomposable with respect to the maximum if f(x, S) = max{f(x, S1), f(x, S2),...,f(x, S(k))} for any decomposition S = [GRAPHICS] Computing the maximum (minimum) value of a decomposable function is inherent in many problems of computational geometry and robotics. In this paper, a general technique is presented for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. Our result holds for a semi-online model of dynamization: When an element is inserted, we are told how long it will stay. Applications of this technique include efficient algorithms for dynamically computing the diameter or closest pair of a set of points, minimum separation among a set of rectangles, smallest distance between a set of points and a set of hyperplanes, and largest or smallest area (perimeter) rectangles determined by a set of points. These problems are fundamental to application areas such as robotics, VLSI masking, and optimization.