Covering 2D data by m squares (alternative to k-means)

Question

Let us have some data $x_i\in\mathbb{R}^2$ for $i=1,\dots,n$. Let $m=1000$. Let a small number is given, e.g. $m=5$.

The goals is to cover $n$ data by $m$ squares of the same size. The size shall be as small as possible.

In the other words $$ \arg\min_{p\in P} a $$ where $$ p = \left(c_{1,1},c_{1,2},\dots,c_{m,1},c_{m,2},a\right)\in\mathbb{R}^{2m+1} $$ are centers of squares and their size. Moreover $$ P=\{p:\forall i=1,\dots,n \; \exists j=1,\dots,m:x_i\in C_j\} $$ where $C_j$ is square given by center $c_{j,1},c_{j,2}$ and size $a$. In the other words, each data point must be covered at least by one square.

My attempt: To use differential evolution to optimize over $P$.

EDIT: Squares cannot be rotated, they are aligned with axes.

Answer 1

This is not a clustering problem, but a set cover type of problem.

These (but so is k-means) are usually NP-hard, so finding the minimum is usually not feasible. Instead, you usually go with a greedy heuristic, and some iterative refinement to find a local optimum.

OTOH, in 2d, it may be of lower complexity.

The problem with using clustering here is that clustering algorithms like HAC and k-means assume that the closest points must be in the same set. But in a set cover problem, it may be desirable to violate this. Consider the set (-1,-1), (-1,1), (1,-1), (1,1), (-0.1,-0.1), (-0.1,0.1), (0.1,-0.1), (0.1,0.1) to be covered by four squares. Any clustering algorithm will attempt to put the four central points into the same cluster because they are close. The resulting cover will then have an edge length of 1.1. But the optimum cover matches each corner with only one of them (i.e. square edge length 0.9).

So try a greedy initialization (e.g. choose the farthest point from the center, then k-1 times the farthest point from all previous points (minimum to all previous, and use maximum norm). Then assign points so they least increase the required square size. Afterwards, try to move points to other squares if this further improves the result until you cannot further improve. This strategy should be okay as a start, but you will want something more random innthe beginning, so you get more than 1 chance to find the optimum.