Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Linear Programming Queries Revisited

MPG-Autoren
/persons/resource/persons45255

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


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