hide
Free keywords:
-
Abstract:
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.
