# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Linear Programming Queries Revisited

##### 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.