## Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 275-298 |

Number of pages | 24 |

Journal | Journal of the ACM (JACM) |

Volume | 38 |

Issue number | 2 |

DOIs | |

State | Published - Jan 4 1991 |

## All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence

## Keywords

- Voronoi diagram
- decomposability
- dynamization
- geometric algorithms
- semi-online model