Another variation of $k$-means problem in the plane

Question

According to wikipedia, consider $k$-means problem in the plane :

k-means clustering aims to partition the $n$ observations into $k (≤ n)$ sets $S = \{S_1, S_2, \dots, S_k\}$ so as to minimize the within-cluster sum of squares. Formally, the objective is to find: $$\min\sum_{i=1}^k\sum_{x\in S_i} \| x − \mu_i \|^2$$

where $\mu_i$ is the mean of points in $S_i$.

We know that there is constant factor approximation algorithm for $k$-means problem. Now, consider this example that we find $3$-means clustering in the plane:

But we want modify the above clusters such that we create such clusters that each cluster has a rectangular shape as bellow:

My question is, can we do some modification on any constant factor approximation algorithm for $k$-means such that give us a rectangular partition and constant factor approximation algorithm? Also, is there any paper about this problem? It seems this problem should be well-studied, but I was unable to find any references.

Answer 1

Assuming P$\ne$NP, there is no such poly-time approximation algorithm.

I assume here that any approximation algorithm must return some feasible $k$-cover, as long as the given input has one. By a $k$-cover of a given set $S$ of points in the plane, I mean a set of $k$ pairwise-disjoint axis-parallel rectangles such that every point in $S$ is in one of the rectangles.

Theorem 1. No such approximation algorithm runs in polynomial time, unless P=NP.

Proof. If there were such an algorithm, it could decide the following decision problem in poly-time: given $(k, S)$, does $S$ have a $k$-cover? (regardless of objective). By Theorem 2 of [1], this decision problem is NP-hard. $~~~\Box$

Remark. The theorem assumes $k$ is part of the input. For any fixed $k$, the problem can be solved in poly-time by exhaustive search, as there are $O(n^4)$ distinct rectangles to consider, so $O(n^{4k})$ possible covers, so there is an exact algorithm that runs in time $n^{4k+O(1)}$.

---

[1] Ahn, Hee-Kap, et al. "Covering points by disjoint boxes with outliers." Computational Geometry 44.3 (2011): 178-190. https://doi.org/10.1016/j.comgeo.2010.10.002