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

• What is a "rectangle" here? The notation "$r\in\mathbb{R}\times\mathbb{R}$" formally implies that $r$ is a single point in the plane. – JeffE Jul 18 '12 at 12:11
• The rectangle $\left(r_x,\: r_y\right)\in\mathbb{R}\times\mathbb{R}$ is the rectangle bound by $\left(0,\: 0\right)$, $\left(r_x,\: 0\right)$, $\left(0,\: r_y\right)$ and $\left(r_x,\: r_y\right)$. – user1534126 Jul 18 '12 at 12:31
• I don't know of any existing data structure that addresses Get. Finding the dominating point (same thing as containing rectangle) $c$ such that $c_x \cdot c_y$ is minimized might be a new question. I would start by trying to design a decomposition scheme to support Get (see here) – Joe Jul 18 '12 at 19:35