Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.