Dynamically Computing the Maxima of Decomposable Functions, with Applications

The authors present a general technique for updating the maximum (minimum) value of a decomposable function as elements are inserted into and deleted from the set S. 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. The main appeal of the approach lies in its generality. Several research directions suggested by the work are noted. >

Authors

• David P. Dobkin
• Subhash Suri

Keywords

• Heuristic algorithms
• Computational geometry
• Robots
• Costs
• Very large scale integration
• Extraterrestrial measurements
• Search problems
• Data structures
• Data Structure
• Value Function
• Perimeter
• Minimum Distance
• Efficient Algorithm
• Hyperplane
• Levels Of Hierarchy
• Minimum Maximum
• Dynamic Algorithm
• Voronoi Diagram
• Recursive Algorithm
• Smallest Area
• Application Of Theorem
• Multivariate Function
• Convex Polygon
• Geometric Objects
• Maximum Minimum Value
• Proof Sketch