Data Structures for Range Minimum Queries in Multidimensional Arrays

by

Hao Yuan

Time: 3pm on Friday, Dec 3
Venue: 4483

Abstract:
Given a multidimensional array, the Range Minimum Query (RMQ) asks for
the minimum element within a contiguous subarray. In this talk, we
will present a data structure that can be built in linear time for a
multidimensional array, such that any range minimum query can be
answered in constant time. At the end of the talk, some open problems
related to the offline RMQ will be discussed.