## Recursive Circle Packing

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

### Recursive Circle Packing

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.

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.

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

### 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(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.

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

### Re: Recursive Circle Packing

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

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