I have large 3 dimensional dataset that I need to classify in a particular way. I'm hoping for something like a k-means clustering method, but instead of inputting the number of clusters I would like to input the maximum radius of a cluster.

Said another way, given a sphere of a defined size, I would like to find the minimum number of non-empty spheres that will cover all the data and classify the points accordingly.

I would like to output a 2D array of the same height and width, with labels that represent the sphere each point in the 3D array was classified in. No two points with the same label should have a euclidian distance greater than the maximum radius, no sphere should be empty, no spheres should overlap and the algorithm should use the minimum number of spheres possible to accomplish this.

Though I have little knowledge of the field, I have been looking into clustering algorithms for a little while and have not found one that accomplishes this.


1 Answer 1


Finding the minimum number of spheres likely makes this problem NP-hard, and a variant of the set cover problem. Good luck. It gets particularly difficult if you want to consider balls tha can be inbetween of data points.

There are two obvious clustering algorithms that will find an approximation: Leader and Complete Linkage Agglomerative Hierarchical Clustering. But they will not find the maximum, only an approximation, and probably with no guarantees.

Also, your assumptions are wrong: if you cover the data with balls of radius r, the maximum distance of two points will be 2*r.


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.