(source: hiveworkshop.com)
In the above picture, I have 20 arbitrary points split into 5 clusters. On the right is a circle that defines the max cluster size. On the top right is the maximum points per cluster. I want to be able to take any arbitrary set of points k and split them into clusters of max sizes n with max radii r. I need the algorithm to retrieve the most full clusters possible (in the above example, as many clusters of 4 as possible). Any given point can only belong to 1 cluster and clusters may not overlap.
It would also be helpful if the algorithm could add/remove points to an existing set and update the clusters.
I am totally lost on how to accomplish this. My best idea so far was calculating centers for sets of points and then using those centers for binary space partitioning, but the best I could hope with using that approach would be evenly distributed clusters.
Any help would be appreciated :).
edit
Don't overlap as in the shapes that regions form don't intersect with the shapes other regions form and that regions are not located inside of other regions (circles in circles for example). In the above picture, each region has a shape to it. None of these shapes intersect and no region is inside of another region.