Maintenance of Geometric Extrema ∈

Let S be a set, f: S×S→R⁺ a bivariate function, and f1991 the maximum value of f(x,y) over all elements y S. We say that f is decomposable with respect with the maximum if f(x,S) = max {f(x,S₁),f(x,S₂),…,f(x,S_k)} for any decomposition S = μ_i=1 ^i=kS_i. 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) retangles determined by a set of points. These problems are fundamental to application areas such as robotics, VLSI masking, and optimization.