Paper Info
Title
Data structures for range minimum queries in multidimensional arrays
Abstract
Given a d-dimensional array A with N entries, the Range Minimum Query (RMQ) asks for the minimum element within a contiguous subarray of A. The 1D RMQ problem has been studied intensively because of its relevance to the Nearest Common Ancestor problem and its important use in stringology. If constant-time query answering is required, linear time and space preprocessing algorithms were known for the 1D case, but not for the higher dimensional cases. In this paper, we give the first linear-time preprocessing algorithm for arrays with fixed dimension, such that any range minimum query can be answered in constant time.
Year
DOI
Venue
2010
10.5555/1873601.1873615
SODA
Keywords
Field
DocType
data structure,motion planning,competitive analysis,computational geometry,lower bound,linear time
Query optimization,Data structure,Combinatorics,Computer science,Upper and lower bounds,Range query (data structures),Computational geometry,Range minimum query,Theoretical computer science,Time complexity,Competitive analysis
Conference
Volume
ISBN
Citations 
135
978-0-89871-698-6
32
PageRank 
References 
Authors
1.37
21
2
Name
Order
Citations
PageRank
Hao Yuan1835.10
Mikhail J. Atallah23828340.54