Smallest set of rectangles describing a set of integer points

Question

Given a set of N-dimensional integer points how do I find the smallest set of N-dimensional cuboids (rectangles in the 2-d case), such that an integer point is in the set of integer points if and only if it's contained in one or more of the cuboids/rectangles. Integer point means a point with integer coordinates.

e.g. given the points (1,0), (2, 0) and (3,1), (4,1) the smallest set of rectangles is (1,0-2,0),(3,1-4,1), see diagram below:

2 .....
1 ...##
0 .##..
  01234

Obviously I could do a brute force search, but I'm looking for a more efficient algorithm, even if it still has high complexity.

Answer 1

There are many approaches to locate existing points:

1. Put the points into a hash map for quick lookup. This is probably the best approach for the general case where you can't know how many holes the points will leave if you try to collect them. In the worst case, you'll get one rectangle per point.

2. If you have one or few Z coordinates, collect the points in a bitmap (1 bit depth). Just turn the pixel in the bitmap on.

3. If you really need to collect the points in rectangles, you must first put them into an ordered set (by coordinate). Iterate over this set many times. Each time, take the first point out of the set. Then look for any point which is a left/right neighbor to the one you already have. If there is one, join them into a (horizontal) line. Grow that line as you get more points.

When there are no points left, do the same for the lines to grow rectangles.

Answer 2

I assume that you are willing to tolerate overlapping rectangles, since if the points are

4 .###.
3 ..#..
2 .###.
1 ..#..
0 .###.
  01234

then you can cover with four overlapping rectangles, but would need five non-overlapping.

How about this algorithm:

For each point, find a largest rectangle containing that point. A largest rectangle is one that can't be made any bigger and still just cover the points. If there are two largest rectangles, just pick one. Store that largest rectangle in some sort of data structure that removes duplicates. After you've finished iterating over all the points, the set of rectangles must cover all the points.

I don't know if this is actually a minimal set of rectangles, but I suspect it is.

Note that in the example above, you would get three rectangles: One vertical and two horizontal.

Answer 3

The general case is NP-hard:
http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1988.21976

It looks like it can be approximated to O(log N). See "A compendium of NP optimization problems" online, search for "MINIMUM RECTANGLE COVER" (sorry, not enough reputation to post more than one hyperlink, yet).

Also, it may be that your particular use case can still be solved efficiently.