Comments on: Blowing bubbles on a plane
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane/
Comments on Ask MetaFilter post Blowing bubbles on a planeTue, 19 Oct 2010 13:26:55 -0800Tue, 19 Oct 2010 13:26:55 -0800en-ushttp://blogs.law.harvard.edu/tech/rss60Question: Blowing bubbles on a plane
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane
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? <br /><br /> My intuition tells me that the result will have something to do with voronoi diagrams, but I'm not sure.<br>
<br>
PS: This isn't for homework.post:ask.metafilter.com,2010:site.168206Tue, 19 Oct 2010 13:20:46 -0800EamoncomputationalgeometryefficientpackingresolvedBy: Chocolate Pickle
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418260
This sounds like a job for a genetic program. A lot of these kinds of optimization problems have no practical algorithm (defined as one that will complete before you die of old age) that can give you God's solution, but genetic algorithms can give you an archangel solution in a surprisingly small amount of time (a few hours).<br>
<br>
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.comment:ask.metafilter.com,2010:site.168206-2418260Tue, 19 Oct 2010 13:26:55 -0800Chocolate PickleBy: Eamon
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418266
Sorry, no, the circles can't overlap. It would be a trivial problem otherwise.<br>
<br>
I imagine that a sweepline algorithm could solve this, but Google is failing me.comment:ask.metafilter.com,2010:site.168206-2418266Tue, 19 Oct 2010 13:30:21 -0800EamonBy: jedicus
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418285
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.comment:ask.metafilter.com,2010:site.168206-2418285Tue, 19 Oct 2010 13:37:17 -0800jedicusBy: GuyZero
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418297
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.comment:ask.metafilter.com,2010:site.168206-2418297Tue, 19 Oct 2010 13:43:18 -0800GuyZeroBy: Eamon
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418301
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.comment:ask.metafilter.com,2010:site.168206-2418301Tue, 19 Oct 2010 13:44:52 -0800EamonBy: GuyZero
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418302
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.<br>
<br>
Although some really odd-shaped regions might not even get the point in the circle in that case. I can't prove it though.comment:ask.metafilter.com,2010:site.168206-2418302Tue, 19 Oct 2010 13:45:25 -0800GuyZeroBy: empath
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418303
This would be more a question for <a href="http://mathoverflow.net/">Math Overflow</a>, I think.comment:ask.metafilter.com,2010:site.168206-2418303Tue, 19 Oct 2010 13:45:34 -0800empathBy: Eamon
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418308
empath: thanks, I think you're right.comment:ask.metafilter.com,2010:site.168206-2418308Tue, 19 Oct 2010 13:48:02 -0800EamonBy: equalpants
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418325
The question doesn't seem fully defined.<br>
<br>
1. Are all the radii required to be the same?<br>
2. Must every point have a circle?<br>
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?)comment:ask.metafilter.com,2010:site.168206-2418325Tue, 19 Oct 2010 14:02:12 -0800equalpantsBy: whatnotever
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418346
A good problem-solving heuristic is to consider simple cases.<br>
<br>
A simple case to consider: Two points, distance d between them, infinite plane (or boundary more than d from each point).<br>
<br>
Two equal circles (intersecting at the Voronoi diagram cell boundary) would cover 2*pi(d/2)^2 = (pi*d^2)/2.<br>
<br>
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.<br>
<br>
So the Voronoi diagram solution (filling to the closest boundary of each cell) won't get you the largest possible area.<br>
<br>
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.comment:ask.metafilter.com,2010:site.168206-2418346Tue, 19 Oct 2010 14:11:26 -0800whatnoteverBy: mhum
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418350
GuyZero: <i>Yes, I think you construct a voroni diagram and then fit the bigest circle centered on the point in each region.</i><br>
<br>
Assuming that "best" covering means "covering the largest area", I'm not sure that this will work.<br>
<br>
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πr<sup>2</sup>. If, instead you have one big circle of radius 2r and one circle of radius zero, you have a total area of 4πr<sup>2</sup>.<br>
<br>
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πr<sup>2</sup> while one big circle and two zero-radius circles still gives you 4πr<sup>2</sup>.<br>
<br>
Voronoi diagrams probably play a role in the solution somehow, but it's not quite as straight forward as that.<br>
<br>
<small>On preview: what whatnotever said</small>comment:ask.metafilter.com,2010:site.168206-2418350Tue, 19 Oct 2010 14:15:19 -0800mhumBy: alk
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418351
suppose you have N points indexed by i=1...N<br>
<br>
you want to put a circle centered at each point of radius r_i<br>
<br>
the total area covered will then by sum(pi * r_i ^2)<br>
<br>
let d_ij be the distance between points i and j. you need r_i + r_j <> 0 for every i.<br>
<br>
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.</>comment:ask.metafilter.com,2010:site.168206-2418351Tue, 19 Oct 2010 14:15:54 -0800alkBy: alk
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418356
typo in the above because of angle brackets. the fourth sentence should read:<br>
<br>
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.comment:ask.metafilter.com,2010:site.168206-2418356Tue, 19 Oct 2010 14:19:01 -0800alkBy: hariya
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418369
So, this is how I would start, and then refine my algorithm from here.<br>
<br>
1. Calculate the distance from each point to its nearest neighbour and sort in a descending order.<br>
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.)<br>
3. Draw the biggest circle I can from the second point with the additional constraint of the circle from the first point.<br>
4. Keep repeating till I exhaust all points.<br>
<br>
I tried it on paper for 3 and 4 points constrained in a rectangle, and it seems to work.comment:ask.metafilter.com,2010:site.168206-2418369Tue, 19 Oct 2010 14:25:09 -0800hariyaBy: GuyZero
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418375
<i>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><br>
<br>
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.<br>
<br>
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.comment:ask.metafilter.com,2010:site.168206-2418375Tue, 19 Oct 2010 14:28:08 -0800GuyZeroBy: alk
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418385
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.comment:ask.metafilter.com,2010:site.168206-2418385Tue, 19 Oct 2010 14:34:09 -0800alkBy: mhum
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418445
GuyZero: <i>if closeness is not a concern and you want maximal coverage</i><br>
<br>
Indeed. The OP did not define what a "best covering" was.comment:ask.metafilter.com,2010:site.168206-2418445Tue, 19 Oct 2010 15:24:11 -0800mhumBy: Eamon
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418878
Found it: http://en.wikipedia.org/wiki/Circle_packing_theorem<br>
<br>
Now I'm going to look for an implementation I can use.comment:ask.metafilter.com,2010:site.168206-2418878Tue, 19 Oct 2010 21:04:16 -0800EamonBy: mhum
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418913
<i>Found it: http://en.wikipedia.org/wiki/Circle_packing_theorem</i><br>
<br>
It's not clear to me how this theorem helps you since it only proves existence. <br>
<br>
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.comment:ask.metafilter.com,2010:site.168206-2418913Tue, 19 Oct 2010 21:44:03 -0800mhumBy: mhum
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418914
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.comment:ask.metafilter.com,2010:site.168206-2418914Tue, 19 Oct 2010 21:46:57 -0800mhumBy: Eamon
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2419095
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.comment:ask.metafilter.com,2010:site.168206-2419095Wed, 20 Oct 2010 05:59:39 -0800EamonBy: DevilsAdvocate
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2419117
<i>For example, if you have just three points, the CPT doesn't tell you anything about the radii of the circles in your packing</i><br>
<br>
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 <i>within</i> its corresponding circle (nor even outside any of the other circles).comment:ask.metafilter.com,2010:site.168206-2419117Wed, 20 Oct 2010 06:53:16 -0800DevilsAdvocateBy: mhum
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2419409
Eamon: <i>I'm looking for a way to find a circle packing that covers the greatest area.</i><br>
<br>
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. <br>
<br>
If you're looking to solve an actual instance of the problem, the <a href="http://en.wikipedia.org/wiki/Quadratic_programming">QP</a> formulation given above by <a href="http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418356">alk</a> 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.comment:ask.metafilter.com,2010:site.168206-2419409Wed, 20 Oct 2010 10:27:26 -0800mhumBy: mhum
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2419686
Also, the algorithm proposed by <a href="http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2418369">hariya</a> 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.comment:ask.metafilter.com,2010:site.168206-2419686Wed, 20 Oct 2010 13:57:18 -0800mhumBy: hariya
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2421541
<a href="http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2419686">mhum</a>, 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.comment:ask.metafilter.com,2010:site.168206-2421541Fri, 22 Oct 2010 06:34:27 -0800hariyaBy: DevilsAdvocate
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2421679
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.<br>
<br>
For example, consider these five points:<br>
A (2,1)<br>
B (2,-1)<br>
C (-2,-1)<br>
D (-2,1)<br>
O (0,0)<br>
<br>
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.<br>
<br>
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.comment:ask.metafilter.com,2010:site.168206-2421679Fri, 22 Oct 2010 08:42:52 -0800DevilsAdvocateBy: Eamon
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2427525
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. <br>
<br>
I could be talked into sharing a pythong-based implementation if anybody else cared.comment:ask.metafilter.com,2010:site.168206-2427525Tue, 26 Oct 2010 14:54:07 -0800EamonBy: mhum
http://ask.metafilter.com/168206/Blowing-bubbles-on-a-plane#2430554
Have you tried throwing a <a href="http://www.numerical.rl.ac.uk/qp/qp.html">QP solver</a> at it?comment:ask.metafilter.com,2010:site.168206-2430554Thu, 28 Oct 2010 16:15:34 -0800mhum