Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. 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 have a load of point data in 3D, and I wish to cluster them like so:

  • Each cluster contains points all of which are at most distance $d$ from another point in the cluster.
  • All points in two distinct clusters are at least distance $d$ from each other.

The distances used are Euclidean distances.

Is this a well known clustering algorithm? If so, what is is called? Thanks.

share|improve this question
up vote 4 down vote accepted

Create a graph in which the points are nodes and two points are connected with an edge if and only if they lie within distance $d$ of each other. Stated in these terms, your criteria become

  • Every node in a cluster of two or more nodes is connected to at least one other node in that cluster.

  • No two points in any disjoint clusters can be connected to each other.

In short, you want to compute the connected components of this graph. Linear-time algorithms are well known and simple to execute, as described in the Wikipedia article.

To do this efficiently for a lot of points in 3D, you want to limit the amount of distance calculation you perform. Data structures such as octrees, or even simpler ones (such as exploiting a lexicographic sorting of the points) work well.

share|improve this answer

Your Answer


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