Please use this identifier to cite or link to this item:
Title: Range Extremum Queries
Authors: Raman, Rajeev
First Published: 19-Jul-2012
Presented at: 23rd International Workshop On Combinatorial Algorithms (IWOCA 2012), Tamil Nadu, India
Start Date: 19-Jul-2012
End Date: 21-Jul-2012
Publisher: Springer Berlin Heidelberg
Citation: Raman, R. ‘Range Extremum Queries’ in Arumugam, S. & Smyth, W. F. (Eds.) Combinatorial Algorithms, LNCS 7643 (© 2012, Springer-Verlag Berlin Heidelberg), pp. 280-287
Abstract: There has been a renewal of interest in data structures for range extremum queries. In such problems, the input comprises N points, which are either elements of a d-dimensional matrix, that is, their coordinates are specified by the 1D submatrices they lie in (row and column indices for d = 2), or they are points in ℝ[superscript d] . Furthermore, associated with each point is a priority that is independent of the point’s coordinate. The objective is to pre-process the given points and priorities to answer the range maximum query (RMQ): given a d-dimensional rectangle, report the points with maximum priority. The objective is to minimze the space used by the data structure and the time taken to answer the above query. This talk surveys a number of recent developments in this area, focussing on the cases d = 1 and d = 2.
Series/Report no.: Lecture Notes in Computer Science;7643
DOI Link: 10.1007/978-3-642-35926-2_30
ISSN: 0302-9743
ISBN: 978-3-642-35925-5
eISSN: 1611-3349
Version: Pre-print
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. The final publication is available at
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
iwoca-abstract.pdfPre-review (submitted draft)228.82 kBAdobe PDFView/Open

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