Maintenance of geometric extrema

Abstract

Let S be a set, f : S × S → R + a bivariate function, and f ( x , S ) 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 1 ), f ( x , S 2 ),…, f ( x , S k )} for any decomposition S = ∪ i =1 i = k S 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.