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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
    
Since you ask for a practical heuristic, how large is $n$? Have you considered applying something like ILP? There's no guarantee it'll be efficient in general, but I suspect it might allow finding an optimal solution for many instances, as long as $n$ isn't too large. – D.W. Apr 18 at 5:08
    
Thanks @D.W. N is about 100. What does ILP stand for? – Andrey Rubshtein Apr 18 at 14:08
    
Integer linear programming. – D.W. Apr 18 at 15:49

This is not an answer to the stated questions, but describes a practical approach you might wish to try when finding numerical solutions to the stated problem.

Consider the following awk script. It reads one or more lines from standard input, in form x y w h, with w and h positive. It outputs one or more lines of form bbox x y w h, each followed by one or more lines of form has x y w h to list the input rectangles contained within that axis-aligned bounding box.

#!/usr/bin/awk -f
NF >= 4 {
    ++rects
    rxmin[rects] = $1
    rymin[rects] = $2
    rxmax[rects] = $1 + $3
    rymax[rects] = $2 + $4
    rindx[rects] = rects
}

END {
    while (length(rindx) > 0) {
        best_area = 0
        best_xmin = 0
        best_ymin = 0
        best_xmax = 0
        best_ymax = 0

        # Construct arrays of unique coordinates
        split("", xminlist)
        split("", yminlist)
        split("", xmaxlist)
        split("", ymaxlist)

        n = 0
        for (i in rindx) {
            xminlist[rxmin[i]] = rxmin[i]
            yminlist[rymin[i]] = rymin[i]
            xmaxlist[rxmax[i]] = rxmax[i]
            ymaxlist[rymax[i]] = rymax[i]
        }

        # Find the largest bounding box that is worth combining
        for (xmin in xminlist)
            for (ymin in yminlist)
                for (xmax in xmaxlist)
                    if (xmax > xmin)
                        for (ymax in ymaxlist)
                            if (ymax > ymin) {
                                area = (xmax - xmin) * (ymax - ymin)
                                if (area > best_area) {

                                    sum = 0.0
                                    for (i in rindx)
                                        if (xmin <= rxmin[i] && ymin <= rymin[i] && xmax >= rxmax[i] && ymax >= rymax[i])
                                            sum += (rxmax[i] - rxmin[i]) * (rymax[i] - rymin[i])

                                    if (sum >= area) {
                                        best_area = area
                                        best_xmin = xmin
                                        best_ymin = ymin
                                        best_xmax = xmax
                                        best_ymax = ymax
                                    }
                                }
                            }

        printf "bbox %.6g %.6g %.6g %.6g\n", best_xmin, best_ymin, best_xmax - best_xmin, best_ymax - best_ymin

        split("", ilist)
        for (i in rindx)
            ilist[i] = i

        for (i in ilist)
            if (best_xmin <= rxmin[i] && best_ymin <= rymin[i] && best_xmax >= rxmax[i] && best_ymax >= rymax[i]) {
                printf " has %.6g %.6g %.6g %.6g\n", rxmin[i], rymin[i], rxmax[i] - rxmin[i], rymax[i] - rymin[i]
                delete rindx[i]
            }
    }
}

The worst-case time complexity of the script is $O(N^7)$, with $O(N)$ space complexity for additional storage.

The idea is to find the largest bounding box where the bounding box area is not greater than the sum of rectangle areas completely contained within the bounding box.

Since each rectangle will be contained in the largest bounding box possible, on each pass we only need to consider rectangles not yet contained in any bounding box.

The tentative bounding boxes are constructed using the unique minimum and maximum $x$ and $y$ coordinates for the rectangles still left. This yields $O(N^4)$ worst-case time complexity. Including testing which rectangles are contained in each tentative bounding box, makes the worst-case time complexity of each pass $O(N^5)$.

Since each pass removes at least one rectangle from those considered, we need at most $N(N-1)$ passes. This makes the overall worst-case time complexity $O(N^7)$.

Unfortunately, I do not know how to prove if this yields an optimal solution.

In particular, if there are solutions where two or more smaller bounding boxes yields a better result than their union, with the union area smaller than the sum of the areas of the rectangles it covers, this approach will not find the optimal solution. Both solutions are valid; it's just that the one with smaller bounding boxes might have smaller sum of bounding box areas, making it a "better" solution.

That might be fixable by selecting the best tentative bounding box not by area, but by the ratio of rectangle area to bounding box area (which is always at least 1 for valid bounding boxes).

share|cite|improve this answer

Your Answer

 
discard

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

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