Skip to main content
eScholarship
Open Access Publications from the University of California

Dynamic three-dimensional linear programming

  • Author(s): Eppstein, David
  • et al.
Abstract

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.

Main Content
Current View