I want to cluster a point cloud in a 3D space (maybe with 200k points). For this I'm locking for a botom up approach.

My goal is, that I can change the granularity of the clustering with a interaction in a user interface and get a fast feedback in visualization.

My first idea is to use a hierarchical cluster algorithm, like average-link. So I can navigate in the depth of the tree if I change the granularity and get a fast feedback. But it take a long time to create such a tree, isn't it O(n^2)?

My next idea is to use a density clustering like OPTICS. But after I change the granularity (here count of clusters), I must recluster all points. This can take a long time to get a feedback?

I also think about a simple kd-tree. This approach is very fast and create a hierarchical tree (like average-link). The problem is, that the kd-tree is only a approximation and I don't know how good the results are..

Has anybody ideas or experiances to clustering points to a cloud? Thank you

  • 1
    $\begingroup$ Could you be more specific what you mean by "granularity"? OPTICS, for example, has only two parameters, the number of points that must make up cluster and an (optional) epsilon that defines the neighbourhood in which to look for other points. What would be granularity here? "Count of clusters" does not make sense to me in this context. $\endgroup$
    – Momo
    Commented Mar 5, 2015 at 12:07
  • $\begingroup$ oh sorry, than I misunderstood OPTICS. With granularity I think about the agglomerative clustering. So In a lower granularity I can merge morge clusters than on a high granularity. Can I create a hierarchy of clusters with OPTICS? $\endgroup$
    – destiny
    Commented Mar 5, 2015 at 12:52
  • 2
    $\begingroup$ Yes, you can generate a hierarchy of clusters from OPTICS. Take a look at the picture here en.wikipedia.org/wiki/OPTICS_algorithm. I'm still not sure what granularity means and what you wnat to achieve; by definition in agglomerative clustering you get every number of clusters between 1 and N at the same time. Perhaps you are only looking for the dendrogam? en.wikipedia.org/wiki/Dendrogram $\endgroup$
    – Momo
    Commented Mar 5, 2015 at 16:59
  • $\begingroup$ Yes, dendrogram. That's the word. Is DeLi-Clu that I'm looking for or what extension can I use? $\endgroup$
    – destiny
    Commented Mar 5, 2015 at 17:10
  • $\begingroup$ I've implemented OPTICS and that's it! has a great performance. Thanks :=) $\endgroup$
    – destiny
    Commented Mar 6, 2015 at 17:28

1 Answer 1


The dendrogram (or the output of OPTICS) needs only O(n) memory to store, and extraction of clusters is O(n). Building the hierarchy is expensive, but you probably need to do this only once.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.