paper329.pdf (339.88 kB)
Succinct indices for range queries with applications to orthogonal range maxima
conference contribution
posted on 2014-10-28, 10:40 authored by Arash Farzan, J. Ian Munro, Rajeev RamanWe consider the problem of preprocessing N points in 2D, each endowed with a priority, to answer the following queries: given a axis-parallel rectangle, determine the point with the largest priority in the rectangle. Using the ideas of the effective entropy of range maxima queries and succinct indices for range maxima queries, we obtain a structure that uses O(N) words and answers the above query in O(logN loglogN) time. This a direct improvement of Chazelle's result from 1985 [10] for this problem - Chazelle required O(N/ε) words to answer queries in O((logN)[superscript 1+ε]) time for any constant ε > 0.
History
Citation
Automata, Languages, and Programming, Lecture Notes in Computer Science, 2012, 7391 LNCS (PART 1), pp. 327-338Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer ScienceSource
39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012Version
- AM (Accepted Manuscript)
Published in
AutomataPublisher
Springer Berlin Heidelbergissn
0302-9743eissn
1611-3349isbn
978-3-642-31593-0;978-3-642-31594-7Copyright date
2012Available date
2014-10-28Publisher DOI
Publisher version
http://link.springer.com/chapter/10.1007/978-3-642-31594-7_28Book series
Lecture Notes in Computer Science;7391Language
enAdministrator link
Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC