Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am given $n$ points in 2D.(Each of say approximately equal weight). I want to partition it into $m$ clusters ($m$ can be anything and it is input by the user) in such a way that the center of mass of each cluster is "far" from center of mass of all other clusters. What is a good heuristic approach (it should also be quick and easy to implement) for this? My current approach is to set up a binary tree at each step. What I am doing now is that the line I choose to separate cluster at each step which maximizes the moment of inertia of the set of points in the cluster I am splitting. Any suggestion welcome!

share|cite|improve this question
up vote 2 down vote accepted

You might want to look at this survey paper on clustering methods:

share|cite|improve this answer

The keyword is "clustering" as mentioned in Moron's answer. Any problem of this type will be NP-complete. In practice, K-means is not bad in its runtime or (depending very much on the application) its results. Like the simplex algorithm for linear programming, it can take exponential time in the worst case, but its practical complexity is much lower. The worst-case bound was proven only very recently.

Also, partitioning a graph is a different problem. Here you are partitioning a set of points and distances are used but not any graph structure.


Here is the smoothed analysis. K-means has polynomial runtime when averaged over (Gaussian) random perturbations of the input, which is not surprising considering the practical efficiency:

share|cite|improve this answer
Thanks Moron and T.. . Yes I know it is NP-complete. I want a efficient heuristic algorithm though. Could you point me to algorithms which are almost linear complexity? (like \mathcal{O}(N \log^{\alpha}N). Thanks for immediate replies. – user17762 Nov 18 '10 at 17:26

You might find K-Means Clustering (and related) helpful.

This is one of the classic machine learning problems, you should find plenty of literature on this.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.