Encircling randomly distributed points

Question

I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly $p$ points. We also (randomly) place $c$ circle centres. I'm trying to find an algorithm that will allow me to find the radii for the circles that cover as many points as possible, subject to the constraints that:

• the radii are bounded (maximum radius $r_{max}$)
• circles cannot intersect/overlap.

My approach so far was to compute a rank 3 tensor. Start from a definition: a point is denied by a circle, if the circle, by taking another point, causes that the point cannot be covered by any of the remaining circles without violating the constraints. The size of tha tensor is $C \times P \times P$, where $C$ is the number of circles, and $P$ is the number of points. I initialize it with zeros. I then check whether if circle c takes point p, point p' is denied, which I signify in the tensor by setting the appropriate value to 1. From this data I'm trying to deduce whether it's worth trying to encircle a point, e.g. if a point is denied by many points, it probably means that it's a distant, isolated point, or that denying point form a cluster. I didn't manage to find a way that would allow me to make general any statements though.

Any ideas how to extend my approach / any suggestions to do it differently would be most welcome!

Answer 1

Okay, I think I have the solution to this one. It exploits the constraint (no overlaps) and the fact, that even a complex, multiple overlap problem, can actully be seen as a bunch of pairwise confilcts - at the end of the day no two circles can overlap.

Here is how it goes: Find all points that can be covered by by a given circle and sotre these. Find the furthest point distance and set the radius of the circle to be that distance. Now we probably have some overlaps. Create a priority queue and enter all the overlaping circles into the queue. The index of the queue is:

(distance from the furthest point) - (distance from the second furthest point).

Then we descrease the radius of the circle with the highest index so that now it's the distance to the second furthest point. Delete the circle from the queue, update the index and re-enter the circle into the queue if it still overlaps with any of the remainging circles. Keep repeating untill there is no more overlap in the system.

The solution is optimal, since the price for retracting the radius is constant (leaving out one point) and the gain is variable (and maximized by teh use of a priority queue).

Answer 2

How about using the convex hull approach and then calculating the centroid of the points that comprise the hull. The distance from the centroid to the furthest point on the hull should give the radius of the smallest circle with the centroid as its center that encompasses all other given points. Here's my algorithm for getting the points on the convex hull (credit Andrew's Monotone Chain algorithm)

# +ve for counter-clockwise rotation
# -ve for clockwise rotation
# 0 for collinear
def cross_prod(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def convex_hull(points):
    points = sorted(set(points))
    lower = upper = []
    for p in points:
        while len(lower) >= 2 and cross_prod(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    for p in points[::-1]:
        while len(upper) >= 2 and cross_prod(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return sorted(set(lower[:-1] + upper[:-1]))