Suggested Final Project Topics

Area Minimum Queries

On Problem Set One, we asked you to design two data structures for the area minimum query problem,

one running in time ⟨O(mn), O(min{m, n})⟩, the other in ⟨O(mn log m log n), O(1)⟩. It turns out that an

⟨O(mn), O(1)⟩-time solution is known to exist, and it's not at all what you'd expect.

Why they're worth studying: For a while it was suspected it was impossible to build an ⟨O(mn), O(1)⟩-

time solution to the area minimum query problem because there was no way to solve the problem using a

Cartesian-tree like solution – but then someone went and found a way around this restriction! Understand-

ing how the attempted lower bound works and how the new data structure circumvents it gives an interest-

ing window into the history of data structure design.