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:

enter image description here

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

enter image description here

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.

  • $\begingroup$ Related: cstheory.stackexchange.com/questions/51177/… (now deleted) $\endgroup$
    – Neal Young
    Mar 22 at 12:02
  • $\begingroup$ @NealYoung Is there any paper about this problem? Or something that give us some hints. I search many times but I can't find any related things about this problem. $\endgroup$
    – All
    Mar 22 at 13:56
  • $\begingroup$ Do you know anyone who can help with this? $\endgroup$
    – All
    Mar 22 at 15:53
  • $\begingroup$ I think the user @Jut has had similar questions, maybe they can help. $\endgroup$
    – Neal Young
    Mar 22 at 19:06

1 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

  • $\begingroup$ It's a great answer. Thank you. $\endgroup$
    – All
    Mar 23 at 23:02
  • $\begingroup$ Can we hope maybe there is or not Pseudo-polynomial time approximation algorithm with constant factor? $\endgroup$
    – All
    Mar 24 at 22:37
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Mar 26 at 2:39
  • $\begingroup$ 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. $\endgroup$
    – Jut
    May 9 at 2:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.