Encircling randomly distributed points

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!

• Do you care more about theoretical worst-case guarantees or performance in practice? If the latter, what's the approximate size of $p$ and $c$? (roughly) And roughly the size of $r_\text{max}$ and the square region? – D.W. Jul 21 '15 at 2:34
• I'm more concerned with the performance in practice. In general, p would be much greater than c. The whole thing is a starting point for simulating a signal coverage using transmitters (c) for receivers (p), so each transmitter could be used by several devices. I think 1:10 ratio would be reasonable. Ideally I'd like to have an algorithm with several adjustable parameters, as I actually want to use it to investigate the system (minimum number of cells to get a reasonabla coverage, etc.), but the maximum range would be up to tens of meters. The square would be ~ few hundred meters each side. – Piotr Jul 21 '15 at 8:29

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).

• I'm not convinced that your solution is optimal. Your algorithm isn't entirely clear either. Do I understand correctly that you shrink the circle for which the difference of the distances from the center of the furthest and second furthest points is largest? – Tom van der Zanden Jul 21 '15 at 10:53
• Yes, that's what I do. If circles overlap, they have to be shrunk. Shrinking is done by giving up on one of the points, since the circle is always just touching the furthest point. If the overlap is complex, it doesn't matter which pairwise conflict will be solved first. For example, if three circles, 1, 2 and 3 overlap, if we resolve 1 and 2, then 1 and 3 and 2 and 3 may or may not still overlap. If they do, then resolve for each pair accordingly. If not, it doesn't mean taht we gave up on points we perhaps did't have to, since these points had to be given up on to resolve 1 and 2. – Piotr Jul 21 '15 at 11:02
• But how do you decide what size to shrink 1 and 2 to to resolve their conflict? Maybe shrinking 2 is better because it resolves the problem with 3, or maybe shrinking 1 is better? – Tom van der Zanden Jul 21 '15 at 11:28
• Right, I didn't see that one. You're of course right. Any ideas on how to improve this? – Piotr Jul 21 '15 at 12:06

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]))

• Welcome to CS.SE! We focus on algorithms, ideas, and concepts here, rather than code. Coding questions are generally off-topic, and we don't want to limit our audience to people who understand a particular programming language or who will pore through a code snippet. Can I encourage you to edit your answer to describe the main ideas? If you feel you need to include code, I suggest you convert the code to pseudocode. See also meta.cs.stackexchange.com/q/64/755. – D.W. Aug 20 '15 at 16:57
• (continued) I see that you have included code for how to compute a convex hull, but how to do that is documented in many standards places, and that's not what the question was asking, so I'm not sure that is going to be helpful. Can I suggest you re-focus your answer on how to use a convex hull algorithm to solve the particular problem listed in the question? Note that the question is not asking for a single circle; instead, we are given $c$ points that are centers of $c$ circles, where possibly $c>1$. So, I think you might have misunderstood the question.... – D.W. Aug 20 '15 at 16:59