# Optimal bounding boxes selection for $N$ rectangles

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: 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?
• 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 '16 at 5:08
• Thanks @D.W. N is about 100. What does ILP stand for? Apr 18 '16 at 14:08
• Integer linear programming.
– D.W.
Apr 18 '16 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).