# Partitioning a graph (clustering of point sets in 2 dimensions)

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!

-

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

http://cchen1.csie.ntust.edu.tw:8080/students/2011/Survey%20of%20clustering%20algorithms.pdf

-

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.