de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Linear Programming Queries Revisited

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45255

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

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

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: http://hdl.handle.net/11858/00-001M-0000-000F-33CD-0
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.