Fixed-dimensional linear programming queries made easy
Timothy M. Chan · 1996
We derive two results from Clarkson's randomized algorithm for linear programming in a fixed dimension d. The first is a simple general method that reduces the problem of answering linear programming queries to the problem of answering halfspace range queries. For example, this yields a randomized data structure with O(n) space and O(n 1\\Gamma1=bd=2c 2 O(log n) ) query time for linear programming on n halfspaces (d ? 3). The second result is a simpler proof of the following: a sequence of q linear programming queries on n halfspaces can be answered in O(n log q) time, if q n ff d for a certain constant ff d ? 0. Unlike previous methods, our algorithms do not require parametric searching. 1 Introduction One of the major discoveries in computational geometry is that fixed-dimensional linear programming can be solved in linear time [Meg84]. It was observed that the introduction of randomization leads to considerably simpler solutions [Sei91, Cla95]. The goal of this paper is...