Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Linear Programming Queries Revisited


Ramos,  Edgar A.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Ramos, E. A. (2000). Linear Programming Queries Revisited. In Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00) (pp. 176-181). New York, USA: ACM Press.

Cite as:
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.