Find two rectangles with minimum areas that cover all points

Question

You're given a n points, unsorted in an array. You're supposed to find two rectangles that cover all points and they should not overlap. Edges of rectangles should be parallel to x or y ordinate.
The program should return the minimum area covered by all these dots. Area of first rectangle + area of second rectangle.

I tried to solve this problem. I sorted points by X ordinate and the first one is the leftmost one of the first rectangle. When we go through the points we find the highest and lowest one. I was thinking that when the difference between two points by x is the biggest, that means that the first point is rightmost one of the first rectangle, and the second point is the leftmost one of the second rectangle.
It should work when the points are given as in first example, however, if the example is the second one it doesn't work. As it would return something like this and that's wrong:

This should be correct:

Then i was thinking doing sorting twice, just, the second time do it by Y ordinate and then compare two total areas. Areas when points are sorted by x and when points are sorted by y and the smaller area is the correct answer.

Answer 1

The two rectangles cannot overlap, so one must be either completely to the right or on top of the other. Your idea to sort the points by x-value and find the biggest gap is good, but you should do that for both directions, as you suggested. That would find the correct rectangles in your example.

The biggest gap isn't necessarily the ideal splitting point, however. Depending on the extent of the bounding boxes in the perpendicular direction, the split may be somewhere else. Consider a rectangular area with four quadrants, where two diagonally opposite quadrants are populated with points:

Here, the ideal split isn't where the largest gap is.

           

You can find the ideal location by considering all possible splits between points with adjacent x- and y-coordinates.

• Sort the points by x-coordinate.
• Scan the sorted array in ascending order. Keep track of the minimum rectangle to the left of the current point by storing the minimum and maximum y-coordinates. Store these running top and bottom borders for each point.
• Now do the same in descending order, where you keep running top and bottom borders for the right rectangle.
• Finally, loop through the points again and calculate the areas of the left and right minimal rectangles for a split between two adjacent nodes. Keep track of the minimum area sum.

Then do the same for minimum top and bottom rectangles. The last two steps can be combined, which will save arrays for the minimum bounds for the right rectangle.

This should be O(n · log n) in time: Sorting is O(n · log n) and the individual passes are O(n). You need O(n) additional memory for the running bounding boxes for thze first rectangle.

Answer 2

The first observation is that any edge of a rectangle must touch one of the points. Edges that didn't touch a point could be pulled back, resulting in less area.

Given n points, there are thus n selections total for left1, right1, bottom1, top1, left2, right2, bottom2 and top2. This gives a simple O(n^8) algorithm already: try all possible assignments and remember the one giving the least total area (right1 - left1)(top1 - bottom1) + (right2 - left2)(top2 - bottom2). Indeed, you can skip any combinations with right < left or top < bottom. This gives a speedup, though it does not change the O(n^8) bound.

Another observation is that the edges should stay within the minimum and maximum X and Y bounds of all points. Find the minimum and maximum X and Y values of any points. Call these minX, maxX, minY and maxY. At least one of your rectangles will need to have its left, right, bottom and top edges, respectively, at those levels.

Because minx, maxX, minY and maxY must be assigned to one of the two rectangles, and there are exactly 2^4 = 16 ways to do this, you can try each of the four possible assignments with the remaining coordinates assigned as above. This gives an O(n^4) algorithm: O(n) to get minX, maxX, minY and maxY, and then O(n^4) to fill in the four unassigned variables for each of 16 assignments of minX, maxX, minY and maxY to the eight edge coordinates.

We have so far ignored the requirement that rectangles not overlap. To accommodate that, we must ensure at least one of the following four conditions holds true:

1. a horizontal line at Y coordinate h with top1 <= h <= bottom2
2. a horizontal line at Y coordinate h with top2 <= h <= bottom1
3. a vertical line at X coordinate w with right1 <= h <= left2
4. a vertical line at X coordinate w with right2 <= h <= left1

The two rectangles overlap if and only if all four of these conditions are simultaneously false. This allows us to skip over candidate solutions, giving a speedup but not changing the asymptotic bound O(n^4). Note that we need to check this condition specifically since, otherwise, optimal solutions might have overlap (exercise: show such an example).

Let's try to shave some more time off of this. Assume we have non-overlapping rectangles by condition #1 above. Then there are n choices for h; we can try each of these n choices and then determine the area of the resulting selections by finding the minimum and maximum coordinates of points in the resulting halves. By trying all n selections for h, we can determine the "best case" vertical split. We need not try condition #2, since the only difference is in the ordering of the rectangles which is arbitrary. We must also try condition #3 with a horizontal split. This suggests an O(n^2) algorithm:

1. For each point, choose h = point.y
2. Separate the points into groups with point.y <= h and point.y > h.
3. Find the minimum and maximum X and Y coordinates of both subsets of points.
4. Compute the sum of the areas of the two rectangles.
5. Remember the minimum area obtained from the above and the corresponding h.
6. Repeat, but using w and X coordinates.
7. Determine whether minimum area was obtained for a vertical or horizontal split
8. Return the corresponding rectangles as the answer

Can we do even better? This is O(n^2) and not O(n) because for each choice of h and w we need to then find the minimum and maximum coordinates of each subgroup. This assumes a linear scan through both subgroups. We don't actually need to do this for the min and max X/Y coordinates when scanning horizontally/vertically, since those will be known. What we need is a solution to this problem:

Given n points and a value h, find the maximum X coordinate of any point whose Y coordinate is no greater than h.

The obvious solution I give above is O(n^2), but you might be able to find an O(n log n) solution by clever application of sorting or maybe even an O(n) solution by some even more clever method. I will not attempt this.

Our solution is O(n^2); the theoretically optimal solution is Omega(n) since you must at least look at all the points. So we're pretty close but there is room for improvement.