Find smallest circle with maximum density of points from a given set

Question

Given the (lat, lon) coordinates of a group of n locations on the surface of the earth, find a (lat, lon) point c, and a value of r > 0 such that we maximize the density, d, of locations per square mile, say, in the surface area described and contained by the circle defined by c and r.

At first I thought maybe you could solve this using linear programming. However, density depends on area depends on r squared. Quadratic term. So, I don't think problem is amenable to linear programming.

Is there a known method for solving this kind of thing? Suppose you simplify the problem to (x, y) coordinates on the Cartesian plane. Does that make it easier?

You've got two variables c and r that you're trying to find so as to maximize the density, which is a function of c and r (and the locations, which is a constant). So maybe a hill-climbing, gradient descent, or simulated annealing approach might work? You can make a pretty good guess for your first value. Just use the centroid of the locations. I think the local maximum you reach from there would be a global maximum.

Answer 1

Steps:

• Cluster your points using a density based clustering algorithm¹;
• Calculate the density of each cluster;
• Recursively (or iteratively) sub-cluster the points in the most dense cluster;
  • The algorithm has to be ignoring the outliers and making them a cluster in their own. This way, all the outliers with high density will be kept and outliers with low density will be weaned out.
• Keep track of the cluster with highest density observed till now. Return when you finally reach a cluster made of a single point.

---

This algorithm will work only when you have clusters like the ones shown below as the recursive exploration will be resulting in similarly shaped clusters:

---

The algorithm will fail with awkwardly shaped clusters like this because as you can see that even though the triangles are most densely placed when you calculate the density in the donut shape, they will report a far lower density wrt the circle centered at [0, 0]:

---

^{1. One density based clustering algorithm that will work for you is DBSCAN.}