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

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.

• Related: cstheory.stackexchange.com/questions/51177/… (now deleted) Mar 22 at 12:02
– All
Mar 22 at 13:56
• Do you know anyone who can help with this?
– All
Mar 22 at 15:53
• I think the user @Jut has had similar questions, maybe they can help. Mar 22 at 19:06

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

• It's a great answer. Thank you.
– All
Mar 23 at 23:02
• Can we hope maybe there is or not Pseudo-polynomial time approximation algorithm with constant factor?
– All
Mar 24 at 22:37
• I don't think so.. Essentially the problem of approximating your problem is as hard or harder than the $k$-cover problem as defined above, which is NP-hard. Approximating your problem in pseudo-poly time is no easier than solving an NP-hard problem in pseudo-poly time. Mar 26 at 2:39
• Is there any reference about k-cover problem? I search in internet but I not found anything about that. Or how we relate above problem to k-cover? Becuase we try to optimize k-means but k-cover have no spicific objective function according your explination.
– Jut
May 9 at 2:23