Finding a known number of circle centers that maximize the number of points within a fixed distance I have a set of 2-D data where I want to find the centers of a specified number of centers of circles ($N$) that maximize the total number of points within a specified distance ($R$).
e.g. I have 10,000 data points $(X_i, Y_i)$ and I want to find the centers of $N=5$ circles that capture as many points as possible within a radius of $R=10$.  The 5 centers and radius of 10 are given beforehand, not derived from the data.
The presence of a data point within a circle is a binary either/or proposition.  If $R=10$, there's no difference in value to a point 11 units away vs. 100 units away, as they are both > 10.  Similarly for being within the circle, there's no extra value to being near the center vs. near the edge.  A data point is either in one of the circles or out.
Is there a good algorithm that can be used to solve this problem?  These seems related to  clustering techniques, but rather than minimizing the average distance, the "distance" function is 0 if the point is within $R$ of any of the $N$ points, and 1 otherwise.
My preference would be to find a way to do this in R, but any approach would be appreciated.
 A: This is a variation k-means problem.  The radius of the centers doesn't matter, as long as their are assumed equal.
Links:


*

*http://en.wikipedia.org/wiki/K-means_clustering

*http://stat.ethz.ch/R-manual/R-devel/library/stats/html/kmeans.html
It will put the centers of the circles at locations of highest probability of the points.  
Classic K-means Procedure:


*

*set cluster count to 5

*put each point in a random cluster

*for each cluster, calculate the mean position

*for each point, calculate the distance to each new mean position

*associate membership with the nearest cluster

*repeat until done (iterations, change in position, or other error metric)


Options:


*

*You can use some under-relaxation after 3, where you translate the mean position slowly toward the new position.

*this is a discrete system so it doesn't converge perfectly.  Sometimes it does and you can end when points stop changing membership, but sometimes they just wiggle a bit.

*If you are making your own code (as most folks should) then you can use the POR k-means above as a starting point, and do some variation on EM informed by percent of points exclusively and completely encompassed by the circles.


Why K-means attacks the problem:


*

*It is the equivalent of fitting a Gaussian Mixture Model where the covariances of the components are equal.  The centers of the mixture components are going to be located at the positions of highest expectation of points.  The curves of constant probability are going to be circles.  This is EM algorithm so it has the asymptotic convergence.  The memberships are hard, not soft.

*I think that if the fundamental assumption of the equal variance components mixture model is reasonably "close", whatever that means, then this method is going to fit.  If you just randomly distribute points, it is less likely to fit well.


There should be some analog of a "Zero Inflated Poisson" where there is a component that is non-gaussian that picks up the uniform distribution.
If you wanted to "tune" you model and were confident that there were enough sample points then you could initialize with the k-means, and then make an augmented k-means adjuster that removes points outside of the radii of the circles from competition.  It would slightly perturb the circles you have, but it might have slightly improved performance given the data.
A: Someone probably has a better formal algorithm, but here's one brute force approach (a hack?).  I'd use one of the hexagonal binning algorithms to compute a 2D histogram. Like hexbin in R. 

I'd use a hexagon size that'd roughly circumscribe your circle of radius R and then sort on the top N bins. If you got N distinct far away bins, great. Now one way is to move about the circle locally on a 2*R scale (in x and y directions) from the center of the top density hexagons. Computing densities can roughly optimize position locally.  This will account for the fact that the hexagons were not a moving window with respect to a fixed origin. 
If all top bins are close by you'd have to have some smarter way of moving your circles in that vicinity.
Note that I can think of several corner cases where such a naive strategy will spectacularly fail. Yet, just a starting point. 
Meanwhile, I hope someone has a better algorithm. 
