Given $\\N$ points in 2D space, one is required to cluster them into $\\M$ clusters, with each cluster of a given size $\\S_m$ such that $\sum S_m = N$, in order to minimize the sum of the distance of the points from centroid of their respective cluster. The clusters (or call them bins) are to be filled completely.

Unaware of the correct approach, I thought of solving this using k-means. In which I will first pick $\\M$ random points and will start assigning the remaining points to each of the clusters, assigning the remaining points to the nearest cluster until a given cluster is full. Then for each of the $\\M$ cluster, get the centroid and recursively iterate till the new centroid of the cluster converges with the starting point of the clusters. But this answer is wrong and it relies on the order of points traversal.

My question is whether there is an approach through k-means using which an approximate answer could be achieved efficiently (like a specific way of points' traversal) or is there any other solution which answers the problem efficiently (some level of approximations are okay).

For my specific case, I am talking about some 300-500 points to be divided into some 10-30 partitions (each roughly of the same size - not a lot of variation there). And the points could be considered to be randomly spread in a unit square.

A special follow-on to this could be a case when $\sum S_m = N - i$ where $\\i$ is a whole number less than $\\N$.

  • $\begingroup$ @D.W. I have edited the post, making my question more explicit and also adding the approach that I have gathered so far. Thank you for the comment. $\endgroup$ – travis bickle Jul 9 '18 at 12:01
  • $\begingroup$ Do you really mean "an approach" or do you mean "an efficient approach"? Are you asking whether there exists a polynomial-time algorithm for this task? It can be done in exponential time. $\endgroup$ – D.W. Jul 9 '18 at 16:18
  • $\begingroup$ I mean an effecient approach. Editing my question to include it. $\endgroup$ – travis bickle Jul 10 '18 at 4:39

Your Answer


Browse other questions tagged or ask your own question.