## 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.