Dynamic Three-Dimensional Linear Programming

Linear programming optimizations on the intersection of k polyhedra in R/sup 3/, represented by their outer recursive decompositions, are performed in expected time O(k log k log n+ square root k log k log/sup 3/ n). This result is used to derive efficient algorithms for dynamic linear programming problems ill which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, an improved solution to the planar 2-center problem, is described. >

Authors

• David Eppstein

Keywords

• Dynamic programming
• Linear programming
• Computer science
• Constraint optimization
• Data structures
• Heuristic algorithms
• Application software
• Time factors
• Dynamic Linear Programming
• Stem Cells
• Data Structure
• Objective Function
• Linear Function
• Time Constant
• Unique Set
• Optimal Point
• Polyhedral
• Linear Problem
• Line Segment
• Linear Time
• Convex Hull
• Log Time
• Dynamic Programming Algorithm
• Polytope
• Online Algorithm