If I have a set of points P in 2D I can compute a minimal bounding circle encapsulating all points in the set. Different methods either approximate the optimal solution or search through all the combinations.
Can I do something similar with multiple circles? I want that each point in P is at least inside one circle and that the circles are as as small as possible (this could be either measured by the sum of the radii or even by the combined volume of the circles). As there are good algorithms to find a single enclosing circle, my first idea is to separate the large set into smaller subsets and find an enclosing circle for each of them. The question becomes: what is a good way to split up the set?
Starting from a single enclosing circle, the other extreme case would be if I use as many circles as I have points in my set. Here I would expect that each point is "enclosed" by exactly one circle. Does someone know how to tackle this problem? The solution does not have to be optimal, but it should scale to 3D and up to 10000 points and 10 spheres.
A good way of splitting the points is $k$-means clustering, applicable in any dimension, where $k$ is the number of spheres desired. A local optimum should roughly correspond to a minimum in the combined spheres' volume.