Please use this identifier to cite or link to this item:
Title: Succinct indices for range queries with applications to orthogonal range maxima
Authors: Farzan, Arash
Munro, J. Ian
Raman, Rajeev
First Published: 2012
Presented at: 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012
Publisher: Springer Berlin Heidelberg
Citation: Automata, Languages, and Programming, Lecture Notes in Computer Science, 2012, 7391 LNCS (PART 1), pp. 327-338
Abstract: We 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.
Series/Report no.: Lecture Notes in Computer Science;7391
DOI Link: 10.1007/978-3-642-31594-7_28
ISSN: 0302-9743
ISBN: 978-3-642-31593-0
eISSN: 1611-3349
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2012, Springer-Verlag Berlin Heidelberg. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper329.pdfPost-review (final submitted)339.88 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.