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

  • $\begingroup$ 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. $\endgroup$ – JeffE Jul 18 '12 at 12:11
  • $\begingroup$ 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)$. $\endgroup$ – user1534126 Jul 18 '12 at 12:31
  • 1
    $\begingroup$ 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) $\endgroup$ – Joe Jul 18 '12 at 19:35

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.