Define the unit square with vertices {(0,0), (0,1), (1,1), (1,0)}. We want to fill this square with circles in a systematic manner as follows:
1. Pick the largest real number, r, such that 0<r<=0.5 and at least one circle of radius r can be placed inside the square without overlapping existing circles.
2. Pack as many circles (of radius r) into the square as possible.
3. Without removing any circles, increment iteration number and return to step 1.
We say a point is "contained" in a circle if the distance from the point to the circle's center is less than or equal to the circle's radius. Will there be any points inside the square that will never be contained in a circle?
Given a point (a,b) inside the square, is there a closed formula that will calculate the iteration at which that point will be contained by a circle?
Note: Due to symmetry we only need to consider (a,b) that lie inside the triangle region {(0,0), (0.5,0.5), (0.5,0)}.
Recursive Circle Packing
Moderators: gmalivuk, Moderators General, Prelates
Recursive Circle Packing
This is a block of text that can be added to posts you make. There is a 300 character limit.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Recursive Circle Packing
On the boundary of the square, only a countable number of points will be included in the circles for obvious reasons. As for everywhere else, after a finite number of steps you always have a closed set, so every point not included will have an open disc around it that isn't in any of the circles. Fix a point and let epsilon be the radius of the open disc around it. Convince yourself that the radii of the added circles is going to 0. And then the argument gets hard. I'll give it a bit of thought and maybe get lucky.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Recursive Circle Packing
Considering only the points on the square's edge is a good strategy. I never thought about that.
Looking only at the circles along the line y = x. If the nth largest circle has radius R(n), then we have R(k+1) = (3  2*sqrt(2))*R(k1). So every number of the form 0.5*(32*sqrt(2))^{k1} can be reached on the kth iteration.
The tricky part is getting the circles that are tangent to to two existing circles. If the curve were exponential, there might be some symmetry to exploit...
Looking only at the circles along the line y = x. If the nth largest circle has radius R(n), then we have R(k+1) = (3  2*sqrt(2))*R(k1). So every number of the form 0.5*(32*sqrt(2))^{k1} can be reached on the kth iteration.
The tricky part is getting the circles that are tangent to to two existing circles. If the curve were exponential, there might be some symmetry to exploit...
This is a block of text that can be added to posts you make. There is a 300 character limit.

 Posts: 449
 Joined: Wed Sep 21, 2011 3:44 am UTC
Re: Recursive Circle Packing
There are uncountably many points that are never included. Let's add in the circles a slightly different way. Start with the empty square, and at each step add in one circle for each distinct region, adding in the largest possible circle in that region. So at step 1 you add the circle circumscribed by the square, at step 2 you add circles in each corner, at step 3 you add circles in the 12 gaps that now exist, and so on. With the exception of step 1, each step n takes each existing gap and splits it in three by inserting a circle. So all the gaps at step n+1 are adjacent to exactly one circle from step n. Thus every circle in this construction can be reached by a unique sequence constructed by starting with the first circle, then choosing one of its adjacent gaps to reach the next circle, and so on. Any point eventually included can be assigned to the circle that includes it and thus likewise corresponds to one of these finite sequences of circles. But since there are always gaps, it is possible to construct an infinite sequence of circles in this manner. Looking at the centers of these circles gives a corresponding infinite sequence of points, which converge to a point that is never included at any step, unless the sequence converges to the boundary of some circle. But that is only the case if, after some step N, every gap choice remains adjacent to a particular circle. Every sequence that doesn't eventually stay adjacent to some circle converges to a point that is never included.
Who is online
Users browsing this forum: No registered users and 15 guests