Dividing 3D points with xyz coordinates in to 10 domains based on spatial proximity

Question

I have a set of xyz coordinates for points distributed on a arbitrary 3D surface.(about 50000) I need to group these points in to 10 domains each containing approximately 1/10th of data points according to spatial proximity. Basically 10 surface patches on the surface. Thanks.

Answer 1

Looks like you want a clustering algorithm.

I has luck with k-means++ before.

See http://en.wikipedia.org/wiki/K-means_clustering for the k-means algorithm

and http://en.wikipedia.org/wiki/K-means%2B%2B for the k-means++ variants.

Answer 2

Take an icosohedron embedded in the sphere. It has 20 equilateral triangle faces.
Pair up neighboring faces. Project the resulting quadrilaterals onto the sphere for your 10 areas. http://en.wikipedia.org/wiki/Icosahedron

Answer 3

With K-means you might get clusters with 0 points in them. It is not hard to handle this degenerate case but I do not know if k-means++ does so. You can also take a look at Cluto, it implements a whole gamut of different clustering algorithms. Hopefully one of them will suit your needs. If you requirements are strict, i.e. you want exactly 10 partitions with 1/10 points in each, use graph partitional clustering algorithms. They are implemented in Cluto as well