Finding a minimal containing rectangle from a given set of rectangles The problem is as follows:

Given a finite set of rectangles ($S\subset\mathbb{R}\times\mathbb{R}$), build a data structure that will support the following operations:


Check, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and returns true iff there is a rectangle $c\in S$ so that $r_x \leq c_x$ and $r_y \leq c_y$.
Get, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and returns the minimal member of $S$ (that is, a member with a minimal area - $c_x c_y$) that contains $r$ (i.e., $r_x \leq c_x$ and $r_y \leq c_y$).
Insert, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and adds it to $S$.
Remove, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and removes it from $S$.


The four procedures have to be efficient, measuring efficiency by $m$ and $n$, where $m$ is the number of different widths in $S$ and $n$ is the number of different heights in $S$.

Space efficiency has to be no worse than $O(mn)$ (that is, linear to the number of elements in $S$).
Check, insert, and remove can be accomplished by a data structure for dynamically maintaining 2D maxima (this 2011 paper by Brodal and Tsakalidis presents a history of the problem including their new algorithm). I have no idea how to do get.