Donald Bren School of Information and Computer Sciences

We perform linear programming optimizations on the intersection of k polyhedra in R^3, represented by their outer recursive decompositions, in expected time O(k log k log n + [square root of] k log k log^3 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 and 2-median problems.