Dynamic Three-Dimensional Linear Programming

We perform linear programming optimizations on the intersection of k polyhedra in R³, represented by their outer recursive decompositions, in expected time O(k log k log n + √k log k log³n). We use this result to derive efficient algorithms for dynamic linear programming problems in which constraints are inserted and deleted, and queries must optimize specified objective functions. As an application, we describe an improved solution to the planar 2-center problem.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.