ORSA Journal on Computing
- Dynamic three-dimensional linear programming.
D. Eppstein.
Tech. Rep. 91-53, ICS, UCI, 1991.
32nd IEEE Symp. Foundations of Comp. Sci., San Juan, Puerto Rico, 1991, pp. 488–494.
ORSA J. Computing 4: 360–368, 1992 (special issue on computational geometry).Uses Dobkin-Kirkpatrick hierarchies to perform linear programming queries in the intersection of several convex polyhedra. By maintaining a collection of halfspaces as several subsets, represented by polyhedra, this leads to algorithms for a dynamic linear program in which updates change the set of constraints. The fully dynamic results have largely been subsumed by Agarwal and Matoušek, but this paper also includes polylog time results for semi-online problems, and uses them to give a fast randomized algorithm for the planar 2-center problem (later improved by various authors, most recently in "Faster Construction of Planar Two-Centers", which re-uses the data structures described here).