Hilfe Wegweiser Impressum Kontakt Einloggen





Linear Programming Queries Revisited


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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

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.

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.