Minimum length of squares to cover k points

Question

This is n=2 case of the question I asked.

Minimum length of n-dimensional cubes to cover k points

let's assume that we have k points

(a11, a12)

(a21, a22)

.
.

(ak1, ak2)

and we're allowed to use x number of squares to cover those points

(if the points are on the square, like they are on side or vertice of the square, or inside the square, then we consider the point to be covered by the square).

If k and x are fixed, and all squares must have the same side length, can we figure out what would be the minimum side length of squares, so that they cover all the points? Squares can overlap, and they must be parallel to the coordinate axes.

For instance, let's k=5, x=2, and the points are (2, 0), (0, 4), (2, 2), (3, 2), (0, 8), then the minimum side length of the squares should be 4, and the square with vertices (0, 0), (0, 4), (4, 0), (4, 4) and one with vertices (4, 0), (4, 4), (8, 4), (8, 0) would cover all the points

I was wondering if there was a well-known algorithm or easy way to do it, and if possible, generalize it to n-dimensional case.

Answer 1

The general problem is similar to the minimum bounding problem, which finds the "oriented minimum bounding box enclosing a set of points". If the points form a convex polygon, an O(n) "algorithm for the minimum-area enclosing rectangle is known". This could be adapted to find the minimum square to cover a set of points.

Your problem would be more difficult since you're dealing with x squares, but it's simplified by the requirement that the squares are parallel to the axes. You need to work out an algorithm to divide the points into x areas so that each area will be able to be covered by the same size square. Let's say X is 4. In such a case, you would look for a line that divides the x-points into 2 equal areas and a line that divides the y-points into 2-equal areas and adjust from there.