ICS Theory Group

March 12, Winter Quarter 2010: Theory Seminar

1:00pm in 1423 Bren Hall

Data Structures for Range Minimum Queries in Multidimensional Arrays

Puneet Mehta, UC Irvine

Presenting a paper by Yuan and Atallah

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.