Maintenance of Geometric Extrema

Abstract:

A general technique is presented for maintaining the extrema of certain functions defined over sets of geometric objects. Maintenance is done as objects are inserted into and deleted from the data set. The technique is illustrated by presenting efficient algorithms for dynamically solving a variety of problems in computational geometry, robotics, VLSI design and operations research.