find minimal number of rectangles to cover 2D point array

Question

I am given an array of 2D points and the task is to generate a minimal list of rectangles, where all rectangles have the same size and orientation, which cover all 2D point positions and can overlap.

So far, I have a rather unsatisfying solution, where the first point in the array is selected as center for the first rectangle and then move the rectangle so the nearest point is going to fit in. That process is repeated until an already covered point would be lost, if the rectangle is to be moved again. After that the process is repeated starting with the next uncovered point until no point is left. Not very satisfying.

The target is to figure out an optimal algorithm. It does not have to be the absolute minimal number of rectangles, but as few as possible.

Answer 1

As only a heuristic solution can do, I would try as follows:

• find the global bounding box of the points;

• cover the bounding box with a regular grid of rectangles, with no overlaps nor gaps.

• if a rectangle happens to be empty, discard it.

You can add a post-processing step, trying to improve:

• select pairs of neighboring rectangles and find the bounding box of the points they cover; if that box fits in a single rectangle, merge the two rectangles.

Note that as the rectangles have the same size and orientation, you can rescale the data so that the rectangles become unit squares. (Also said by trincot.)