Fitting circles into a circle

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
HenryS
Posts: 199
Joined: Mon Nov 27, 2006 9:16 am UTC
Location: Melbourne
Contact:

Fitting circles into a circle

Postby HenryS » Wed May 05, 2010 8:51 pm UTC

I don't think this has been asked before...

Suppose you have an open circular disk [imath]D[/imath] in the Euclidean plane.

Suppose I give you a finite collection [imath]\{D_1, D_2, \ldots, D_n\}[/imath] of open circular disks whose total area is at most half the area of [imath]D[/imath]. Can you always arrange these disks to fit inside of [imath]D[/imath], without any overlaps between the [imath]D_i[/imath]?

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: Fitting circles into a circle

Postby BlackSails » Wed May 05, 2010 10:53 pm UTC

Lets look at the limit of big and small subcircles. In the limit of small circles, you just have points with total area equal to half the circle, and they easily fit. In the limit of big circles, you have one circle with half the area, which easily fits. In the middle, you have a bunch of circles of medium size, which I guess is that hard case to do with rigor, but the small and big circles both fit, so I dont see why the intermediate case wouldnt.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Fitting circles into a circle

Postby WarDaft » Thu May 06, 2010 3:43 am UTC

Either this is one of those things where it seems obvious but is almost impossible to prove, there's some quirk of geometry I'm not familiar with that makes the problem with an open disc more complicated than just a circle, or it's just a trivial result of circular packing density being higher than 50%. As these are the XKCD forums, it is almost certainly one of the first two.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Fitting circles into a circle

Postby NathanielJ » Thu May 06, 2010 4:11 am UTC

BlackSails wrote:Lets look at the limit of big and small subcircles. In the limit of small circles, you just have points with total area equal to half the circle, and they easily fit. In the limit of big circles, you have one circle with half the area, which easily fits. In the middle, you have a bunch of circles of medium size, which I guess is that hard case to do with rigor, but the small and big circles both fit, so I dont see why the intermediate case wouldnt.


But you could use that exact same logic to say that in the two "extreme" cases, as long as the combined area of the D_i is no greater than the large circle, they fit. This clearly is not the case for the in-between cases though.

Edit: If it matters, I believe that the conjecture is true for density 50%. However, it should be noted that there are simple counterexamples for any density greater than 50% (and thus circle packing likely doesn't come into play).
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

User avatar
HenryS
Posts: 199
Joined: Mon Nov 27, 2006 9:16 am UTC
Location: Melbourne
Contact:

Re: Fitting circles into a circle

Postby HenryS » Thu May 06, 2010 2:18 pm UTC

The first example to think about is two circles of half radius of the original. Their total area is exactly half of the original circle, and they only just fit, so 50% is an upper bound on what could be possible.

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Re: Fitting circles into a circle

Postby BlackSails » Thu May 06, 2010 2:26 pm UTC

Yeah, I was thinking only about density <= 50%.

User avatar
eta oin shrdlu
Posts: 451
Joined: Sat Jan 19, 2008 4:25 am UTC

Re: Fitting circles into a circle

Postby eta oin shrdlu » Sun May 09, 2010 5:29 am UTC

As a simple special case, if all the [imath]D_i[/imath] have the same radius [imath]\frac1{\sqrt{2n}}[/imath], then you can always fit the n disks in concentric annuli (starting from the outside of the large disk, and working inward as necessary--for 12 or fewer you just need one ring, for 13-48 you need two rings, and so on). For large n this gives a packing density of [imath]\frac\pi4>\frac12[/imath], not as good as the hexagonal close-packing arrangement, but it's easier to handle the circular boundary this way; use inequalities to show it works for all n>N, then just check explicitly that it works up to N.

I don't have any good ideas about handling the general case, though.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests