Linear Programming Queries Revisited

We describe an approach for answering linear programming queries with respect to a set of $n$ linear constraints in $\Re^d$, for a fixed dimension $d$. Solutions to this problem had been given before by Matou\v{s}ek (1993) using a multidimesional version of parametric search and by Chan (1996) using randomization and Clarkson's approach to linear programming. These previous approaches use data structures for halfspace-range emptiness queries and reporting queries, respectively. Our approach is a generalization of Chan's: it also uses halfspace-range reporting data structures, Clarkson's approach to linear programming, and avoids parametric search; unlike Chan's appraoch, it gives deterministic solutions without considerable additional preprocessing overhead. The new solution is as good or improves the previous solutions in all the range of storage space: with $O(n^{\fdh} \log^{O(1)} n)$ storage space, it achieves query time $O(\log^{ c \log d} n)$, where $c$ is a small constant independent from $d$, in comparison to $O(\log^{d+1} n)$ for Matou\v{s}ek's data structure and $O(n^{c'\log d})$ for Chan's; with $O(n)$ storage space, it achieves, as Chan's data structure, query time $O(n^{1-\ifdh} 2^{O(\log^* n)})$ after $O(n^{1+\epsilon})$ preprocessing, but without using randomization