Suppose that I have $n$ straight rectangles on a plane $r_i = (x_i,y_i,w_i,h_i)$. Each rectangle has a cost function, its area $A(r_i) = w_i \cdot h_i $. I can also "merge" 2 or more rectangles into their bounding box. In this case the cost function will be the area of the bounding box, instead of the sum of their areas.

The optimization problem is:

Let $R = \{r_1,r_2,\ldots,r_n\}$

Let $p = \{R_1, R_2,\ldots,R_k \} $ be a partition of the set of rectangles such that $ \forall i,j : R_i \cap R_j = \emptyset $ and $ \cup R_i = R $

Then, the following functional should be minimized:

$f(p) = \Sigma A(R_i) $, where $ A(R_i) $ is the area of the bounding box of the subset.

I would like to find a fast algorithm that finds the optimal solution.

For example: In a special case of two squares $(x,y,s,s),(x',y',s,s) $ with same area, there are only 2 options, merge or not merge. It is better to merge when the area of the bounding box is smaller than the sum of the areas, $ (x'-x+s)\cdot (y'-y+s) \le 2s^2 $. This happens when these two squares have a sufficient overlap.

A naive algorithm would be checking every possible partition and choose the best. It will take an exponential amount of time.

At first I thought of this simple iterative algorithm:

For every pair of rectangles $r_i,r_j$

If merging them will improve the functional,

Merge them, and update the set of rectangles

Until there isn't any pair that will improve the functional

But then I found a counter example in which this algorithm will not find an optimal solution:

enter image description here

Merging any two rectangles in this example will not improve the functional. But merging all of the rectangles into one bounding box will be the optimal solution.

I am currently thinking of sorting both the $x$ and $y$ coordinates and attempting to choose a pair of points on this grid, and to check whether it is advantageous to merge all rectangles inside it.

So my questions are:

  1. Is it a known problem in computational geometry?
  2. Can this problem be proved to be NP hard?
  3. Is there any good practical heuristic to solve it?

Note: The same question was also posted on math.stackexchange, but I was unable to get any good answers.

  • $\begingroup$ Also posted on Math.SE. Please do not post the same question on multiple sites. If you prefer to have the question appear over here, please flag it for moderator attention on Math.SE and ask them to migrate it here -- but please don't cross-post; your question shouldn't be simultaneously open on two different SE sites. $\endgroup$ – D.W. Apr 18 '16 at 5:04

Your Answer

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

Browse other questions tagged or ask your own question.