Blowing bubbles on a plane
October 19, 2010 1:20 PM
Given a set of points on a plane (or in a bounded region), how do I find the radii of circles centered at each point that provide the best covering?
My intuition tells me that the result will have something to do with voronoi diagrams, but I'm not sure.
PS: This isn't for homework.
My intuition tells me that the result will have something to do with voronoi diagrams, but I'm not sure.
PS: This isn't for homework.
Sorry, no, the circles can't overlap. It would be a trivial problem otherwise.
I imagine that a sweepline algorithm could solve this, but Google is failing me.
posted by Eamon at 1:30 PM on October 19, 2010
I imagine that a sweepline algorithm could solve this, but Google is failing me.
posted by Eamon at 1:30 PM on October 19, 2010
Some additional clarification would be useful. For example, does every point have to have a circle centered on it? Otherwise you'd just pick the point nearest the centroid of the convex hull defined by the points and blow up its radius to cover all the points.
posted by jedicus at 1:37 PM on October 19, 2010
posted by jedicus at 1:37 PM on October 19, 2010
Yes, I think you construct a voroni diagram and then fit the bigest circle centered on the point in each region. Some portions of the plane inside the bounding polygon will go uncovered.
posted by GuyZero at 1:43 PM on October 19, 2010
posted by GuyZero at 1:43 PM on October 19, 2010
Let's say that a circle "covers" another even if the second circle has zero radius. I imagine that this constraint would result in no points without circles, but I'm willing to be wrong on that one.
posted by Eamon at 1:44 PM on October 19, 2010
posted by Eamon at 1:44 PM on October 19, 2010
If you want to have the point be inside the circle but not necessarily centered on the point then you just fit the maximum circle inside each polygon in the voroni diagram.
Although some really odd-shaped regions might not even get the point in the circle in that case. I can't prove it though.
posted by GuyZero at 1:45 PM on October 19, 2010
Although some really odd-shaped regions might not even get the point in the circle in that case. I can't prove it though.
posted by GuyZero at 1:45 PM on October 19, 2010
This would be more a question for Math Overflow, I think.
posted by empath at 1:45 PM on October 19, 2010
posted by empath at 1:45 PM on October 19, 2010
The question doesn't seem fully defined.
1. Are all the radii required to be the same?
2. Must every point have a circle?
3. What are you trying to cover--the points, or the plane area? What are the criteria for the "best" covering? (Fewest circles? Smallest maximum radius? Least area covered, while still hitting all the points?)
posted by equalpants at 2:02 PM on October 19, 2010
1. Are all the radii required to be the same?
2. Must every point have a circle?
3. What are you trying to cover--the points, or the plane area? What are the criteria for the "best" covering? (Fewest circles? Smallest maximum radius? Least area covered, while still hitting all the points?)
posted by equalpants at 2:02 PM on October 19, 2010
A good problem-solving heuristic is to consider simple cases.
A simple case to consider: Two points, distance d between them, infinite plane (or boundary more than d from each point).
Two equal circles (intersecting at the Voronoi diagram cell boundary) would cover 2*pi(d/2)^2 = (pi*d^2)/2.
One circle w/ zero radius and the other extending to touch the first point would cover pi*d^2. This is the maximum coverage for this instance.
So the Voronoi diagram solution (filling to the closest boundary of each cell) won't get you the largest possible area.
This feels like it's NP-Hard. Well... you can get linear constraints out of it easily enough (for any pair of points, the sum of the radii for those points must be less than or equal to the distance between them), but the objective function, covered area, is non-linear. Perhaps there's a clever way to linearize it.
posted by whatnotever at 2:11 PM on October 19, 2010
A simple case to consider: Two points, distance d between them, infinite plane (or boundary more than d from each point).
Two equal circles (intersecting at the Voronoi diagram cell boundary) would cover 2*pi(d/2)^2 = (pi*d^2)/2.
One circle w/ zero radius and the other extending to touch the first point would cover pi*d^2. This is the maximum coverage for this instance.
So the Voronoi diagram solution (filling to the closest boundary of each cell) won't get you the largest possible area.
This feels like it's NP-Hard. Well... you can get linear constraints out of it easily enough (for any pair of points, the sum of the radii for those points must be less than or equal to the distance between them), but the objective function, covered area, is non-linear. Perhaps there's a clever way to linearize it.
posted by whatnotever at 2:11 PM on October 19, 2010
GuyZero: Yes, I think you construct a voroni diagram and then fit the bigest circle centered on the point in each region.
Assuming that "best" covering means "covering the largest area", I'm not sure that this will work.
Consider the case of just two points separated by distance 2r. With a Voronoi approach, you would have two circles of radius r, which gives a total area of 2πr2. If, instead you have one big circle of radius 2r and one circle of radius zero, you have a total area of 4πr2.
Similarly, consider three points at the corners of an equilateral triangle with side length 2r. The Voronoi approach gives you a total area of 3πr2 while one big circle and two zero-radius circles still gives you 4πr2.
Voronoi diagrams probably play a role in the solution somehow, but it's not quite as straight forward as that.
On preview: what whatnotever said
posted by mhum at 2:15 PM on October 19, 2010
Assuming that "best" covering means "covering the largest area", I'm not sure that this will work.
Consider the case of just two points separated by distance 2r. With a Voronoi approach, you would have two circles of radius r, which gives a total area of 2πr2. If, instead you have one big circle of radius 2r and one circle of radius zero, you have a total area of 4πr2.
Similarly, consider three points at the corners of an equilateral triangle with side length 2r. The Voronoi approach gives you a total area of 3πr2 while one big circle and two zero-radius circles still gives you 4πr2.
Voronoi diagrams probably play a role in the solution somehow, but it's not quite as straight forward as that.
On preview: what whatnotever said
posted by mhum at 2:15 PM on October 19, 2010
suppose you have N points indexed by i=1...N
you want to put a circle centered at each point of radius r_i
the total area covered will then by sum(pi * r_i ^2)
let d_ij be the distance between points i and j. you need r_i + r_j <> 0 for every i.
you need to optimize the area covered subject to these constraints. there would be various ways to do this, but setting up the problem is pretty simple if you are given d_ij.
posted by alk at 2:15 PM on October 19, 2010
you want to put a circle centered at each point of radius r_i
the total area covered will then by sum(pi * r_i ^2)
let d_ij be the distance between points i and j. you need r_i + r_j <> 0 for every i.
you need to optimize the area covered subject to these constraints. there would be various ways to do this, but setting up the problem is pretty simple if you are given d_ij.
posted by alk at 2:15 PM on October 19, 2010
typo in the above because of angle brackets. the fourth sentence should read:
let d_ij be the distance between points i and j. you need r_i + r_j less than d_ij for every i,j so that the circles don't overlap. you also need r_i greater than 0 for every i.
posted by alk at 2:19 PM on October 19, 2010
let d_ij be the distance between points i and j. you need r_i + r_j less than d_ij for every i,j so that the circles don't overlap. you also need r_i greater than 0 for every i.
posted by alk at 2:19 PM on October 19, 2010
So, this is how I would start, and then refine my algorithm from here.
1. Calculate the distance from each point to its nearest neighbour and sort in a descending order.
2. Draw the biggest circle I can using the first point that satisfies all constraints (lies within the boundary, minimum radius of circle at other points, etc.)
3. Draw the biggest circle I can from the second point with the additional constraint of the circle from the first point.
4. Keep repeating till I exhaust all points.
I tried it on paper for 3 and 4 points constrained in a rectangle, and it seems to work.
posted by hariya at 2:25 PM on October 19, 2010
1. Calculate the distance from each point to its nearest neighbour and sort in a descending order.
2. Draw the biggest circle I can using the first point that satisfies all constraints (lies within the boundary, minimum radius of circle at other points, etc.)
3. Draw the biggest circle I can from the second point with the additional constraint of the circle from the first point.
4. Keep repeating till I exhaust all points.
I tried it on paper for 3 and 4 points constrained in a rectangle, and it seems to work.
posted by hariya at 2:25 PM on October 19, 2010
The Voronoi approach gives you a total area of 3πr2 while one big circle and two zero-radius circles still gives you 4πr2.
I sort of assumed there could be no zero-radius circles. The Voronoi-type solution guarantees that each point covered by a circle is closest to the point its circle is centered on, unlike the zero-radius solution where a point in a given circle might be closer to another point than it's circle's center.
But if closeness is not a concern and you want maximal coverage while allowing some circles to be zero area then it's a whole different algorithm. You'll need a real computational geometer.
posted by GuyZero at 2:28 PM on October 19, 2010
I sort of assumed there could be no zero-radius circles. The Voronoi-type solution guarantees that each point covered by a circle is closest to the point its circle is centered on, unlike the zero-radius solution where a point in a given circle might be closer to another point than it's circle's center.
But if closeness is not a concern and you want maximal coverage while allowing some circles to be zero area then it's a whole different algorithm. You'll need a real computational geometer.
posted by GuyZero at 2:28 PM on October 19, 2010
the approach i described above could be solved with numerical optimization, but you might also be able to approach it analytically. i've never dealt with them, but the karush-kuhn-tucker conditions generalize lagrange multipliers to inequality constraints, which is what you have in this problem. i'm not sure if it's an issue that you have O(N^2) constraints and only N variables. that's where i'd start with this problem.
posted by alk at 2:34 PM on October 19, 2010
posted by alk at 2:34 PM on October 19, 2010
GuyZero: if closeness is not a concern and you want maximal coverage
Indeed. The OP did not define what a "best covering" was.
posted by mhum at 3:24 PM on October 19, 2010
Indeed. The OP did not define what a "best covering" was.
posted by mhum at 3:24 PM on October 19, 2010
Found it: http://en.wikipedia.org/wiki/Circle_packing_theorem
Now I'm going to look for an implementation I can use.
posted by Eamon at 9:04 PM on October 19, 2010
Now I'm going to look for an implementation I can use.
posted by Eamon at 9:04 PM on October 19, 2010
Found it: http://en.wikipedia.org/wiki/Circle_packing_theorem
It's not clear to me how this theorem helps you since it only proves existence.
First, you need to start with some planar graph based around your points. So let's say that you use the Delaunay triangulation (since it seems natural). The Circle Packing theorem states that you can find a circle packing whose intersection graph is, say, the Delaunay triangulation of your points. But, it doesn't actually specify things like the radius of the circles in the packing. For example, if you have just three points, the CPT doesn't tell you anything about the radii of the circles in your packing, just that there exists some packing of three circles such that they are all co-tangent. In fact, every combination of three co-tangent circles, no matter what the radii would, satisfy the conditions.
posted by mhum at 9:44 PM on October 19, 2010
It's not clear to me how this theorem helps you since it only proves existence.
First, you need to start with some planar graph based around your points. So let's say that you use the Delaunay triangulation (since it seems natural). The Circle Packing theorem states that you can find a circle packing whose intersection graph is, say, the Delaunay triangulation of your points. But, it doesn't actually specify things like the radius of the circles in the packing. For example, if you have just three points, the CPT doesn't tell you anything about the radii of the circles in your packing, just that there exists some packing of three circles such that they are all co-tangent. In fact, every combination of three co-tangent circles, no matter what the radii would, satisfy the conditions.
posted by mhum at 9:44 PM on October 19, 2010
Or, another way to put it, since the Circle Packing theorem only guarantees uniqueness up to Mobius transformations, it doesn't really tell you anything about the actual sizes of the circles in your packing, just their relative arrangement.
posted by mhum at 9:46 PM on October 19, 2010
posted by mhum at 9:46 PM on October 19, 2010
Ah, you're right. But I feel like I'm getting closer. At least now I can say that, given a set of points, I'm looking for a way to find a circle packing that covers the greatest area.
posted by Eamon at 5:59 AM on October 20, 2010
posted by Eamon at 5:59 AM on October 20, 2010
For example, if you have just three points, the CPT doesn't tell you anything about the radii of the circles in your packing
Nor does it say that the points lie at the center of the circles in the packing, nor for that matter, that a point even lies within its corresponding circle (nor even outside any of the other circles).
posted by DevilsAdvocate at 6:53 AM on October 20, 2010
Nor does it say that the points lie at the center of the circles in the packing, nor for that matter, that a point even lies within its corresponding circle (nor even outside any of the other circles).
posted by DevilsAdvocate at 6:53 AM on October 20, 2010
Eamon: I'm looking for a way to find a circle packing that covers the greatest area.
Well, now that that's established, I don't think you can avoid zero-radius circles or, at least, specifying a minimum radius for each circle.
If you're looking to solve an actual instance of the problem, the QP formulation given above by alk should be fine. If you're looking for a general, closed-form solution or maybe a specific algorithm, that'll probably require some more thinking.
posted by mhum at 10:27 AM on October 20, 2010
Well, now that that's established, I don't think you can avoid zero-radius circles or, at least, specifying a minimum radius for each circle.
If you're looking to solve an actual instance of the problem, the QP formulation given above by alk should be fine. If you're looking for a general, closed-form solution or maybe a specific algorithm, that'll probably require some more thinking.
posted by mhum at 10:27 AM on October 20, 2010
Also, the algorithm proposed by hariya might be promising, but needs work. Consider the case of 5 points, 4 on the corners of a square and one in the center. Each point has the same distance to its nearest neighbor but depending on whether you start with the center point or one of the corner points, you get much different answers.
posted by mhum at 1:57 PM on October 20, 2010
posted by mhum at 1:57 PM on October 20, 2010
mhum, That is a valid point but can be easily accommodated. If there are multiple points with the same distance to their nearest neighbour, then we just need to add their distance to the boundary or other constraints as additional sorting criteria.
posted by hariya at 6:34 AM on October 22, 2010
posted by hariya at 6:34 AM on October 22, 2010
Working off of mhum's suggestion, I was able to find a case where hariya's method fails. Modify mhum's configuration, so that instead of 4 points in a square with a fifth at the center, you have 4 points in a rectangle with a fifth at the center, such that the short side of the rectangle is slightly shorter than the distance from a corner of the rectangle to its center.
For example, consider these five points:
A (2,1)
B (2,-1)
C (-2,-1)
D (-2,1)
O (0,0)
The distance to each point's nearest neighbor is √5≈2.236 for O, and 2 for each of the other four points. Thus, hariya's algorithm would give a circle of radius √5 around O and radius 0 around the other four points, for a total coverage of 5Π≈15.708.
However, a better solution is circles of radius 2 around points A and C, radius 0 around B and D, and radius √5-2 around O, for a total coverage of 4Π+4Π+(9-4√5)Π≈25.308.
posted by DevilsAdvocate at 8:42 AM on October 22, 2010
For example, consider these five points:
A (2,1)
B (2,-1)
C (-2,-1)
D (-2,1)
O (0,0)
The distance to each point's nearest neighbor is √5≈2.236 for O, and 2 for each of the other four points. Thus, hariya's algorithm would give a circle of radius √5 around O and radius 0 around the other four points, for a total coverage of 5Π≈15.708.
However, a better solution is circles of radius 2 around points A and C, radius 0 around B and D, and radius √5-2 around O, for a total coverage of 4Π+4Π+(9-4√5)Π≈25.308.
posted by DevilsAdvocate at 8:42 AM on October 22, 2010
For anybody still paying attention, once I gave up on finding an algorithm that guaranteed a best solution, I just coded it up to use gradient descent. It runs fairly fast for post sets of points, but can definitely get bogged down or stuck in local minima.
I could be talked into sharing a pythong-based implementation if anybody else cared.
posted by Eamon at 2:54 PM on October 26, 2010
I could be talked into sharing a pythong-based implementation if anybody else cared.
posted by Eamon at 2:54 PM on October 26, 2010
This thread is closed to new comments.
By the way, is it permitted that the circles overlap? Is there any limit on how big they can be? Is there anything other than coverage that you're trying to optimize? As you describe the problem, the answer is easy: put a circle around every point, with an infinite radius.
posted by Chocolate Pickle at 1:26 PM on October 19, 2010