Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 Author, Editor
 Author(s): Ramos, Edgar A. dblp
 Editor(s):
 BibTeX cite key*: Ramos2000d
 Title, Booktitle
 Title*: Linear Programming Queries Revisited Booktitle*: Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)
 Event, URLs
 Conference URL:: http://www.cs.ust.hk/tcsc/scg00.html Downloading URL: http://www.mpi-sb.mpg.de/~ramos Event Address*: Clear Water Bay, Kowloon, Hong Kong Language: English Event Date* (no longer used): June 12-14, 2000 Organization: Association of Computing Machinery (ACM) Event Start Date: 12 June 2000 Event End Date: 14 June 2000
 Publisher
 Name*: ACM Press URL: Address*: New York, USA Type:
 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: June Pages: 176-181 Year*: 2000 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:
 (LaTeX) 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. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Ramos2000d,
AUTHOR = {Ramos, Edgar A.},
TITLE = {Linear Programming Queries Revisited},
BOOKTITLE = {Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)},
PUBLISHER = {ACM Press},
YEAR = {2000},
ORGANIZATION = {Association of Computing Machinery (ACM)},
PAGES = {176--181},
ADDRESS = {Clear Water Bay, Kowloon, Hong Kong},
MONTH = {June},
}