Recursive Circle Packing

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Recursive Circle Packing

Postby Cradarc » Sat Jan 02, 2016 7:52 pm UTC

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)}.
This is a block of text that can be added to posts you make. There is a 300 character limit.

User avatar
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

Postby jestingrabbit » Sat Jan 02, 2016 9:06 pm UTC

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.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Recursive Circle Packing

Postby Cradarc » Sat Jan 02, 2016 10:24 pm UTC

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(k-1). So every number of the form 0.5*(3-2*sqrt(2))k-1 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.

User avatar
PM 2Ring
Posts: 3640
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

Re: Recursive Circle Packing

Postby PM 2Ring » Sun Jan 03, 2016 5:13 am UTC

Descartes theorem is useful to find the radius and location of these circles.

Image

arbiteroftruth
Posts: 436
Joined: Wed Sep 21, 2011 3:44 am UTC

Re: Recursive Circle Packing

Postby arbiteroftruth » Mon Jan 04, 2016 9:58 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests