You are not logged in.
Pages: 1
#1 2005-11-10 06:07:31
- nbrewer
- Novice
Offline
Finding the container circle of multiple circles (A circle packing Q)
I am just starting to investige the wonderful world of circle packing and am trying to figure out how to find the smallest circle which will contain multiple smaller circles. The smaller circles range in radius from 1 to n. I've found a way to get real close, but no cigar. My trig skills are a bit rusty, but still intact.
I wish this forum allowed files to be uploaded so I could show an image. If anyone needs further clarification or an image, just let me know.
Thanks in advance.
#2 2005-11-10 06:18:54
- mathsyperson
- Moderator
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
Umm, they do. When you post, there's a bit just below the post box labelled 'Image Upload'.
And an image would help immensely. 
Why did the vector cross the road?
It wanted to be normal.
#3 2005-11-10 06:27:09
- nbrewer
- Novice
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
I still dont see any option to upload an image, but did see how to use the [ i m g ] tags. So, here you are:
As you see, the container circle could be a bit smaller.
The circles go from radius 1 to radius 5.
Last edited by nbrewer (2005-11-10 06:28:45)
#4 2005-11-10 07:11:37
- mathsyperson
- Moderator
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
Ooh, you're right. I tried it as a guest, and the box with the image upload option doesn't appear. Maybe it only works for mods.
Back to the question, it seems tough. All I can say by thinking is that the container's radius has to be at least the total of the biggest two circles' radii, but you didn't need me to tell you that.
Calling the number of circles n and the smallest container radius r, I've got this so far:
n | r
-------------------------------------------
1 | 1
2 | 3
3 | ?
Pretty pathetic, really. I'll try to work out some more stuff, so we can try to find a pattern.
Why did the vector cross the road?
It wanted to be normal.
#5 2005-11-10 07:29:33
- mathsyperson
- Moderator
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
While googling to see if I could find anything useful, I found this quite good picture:
[Each number represents 1 ÷ radius]
Even if it doesn't help, it's still cool!
Why did the vector cross the road?
It wanted to be normal.
#6 2005-11-10 07:33:10
- nbrewer
- Novice
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
That is only true on smaller n's, and only if the two circles are touching. But, the circles could have any coordinates. Basically I need to find a container circle with it's center at origin, and it's radius large enough to contain all circles 1 -> n.
Example:
Yes... now you are seeing why this is tripping me up.... 
Last edited by nbrewer (2005-11-10 07:42:16)
#7 2005-11-10 07:51:11
- MathsIsFun
- Administrator
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
BTW, nbrewer, you should be able to do image uploads now.
Click "Post Reply", and you should see an "Upload Slots" selector. Have a go and tell me if it works for you.
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..." - Leon M. Lederman
#9 2005-11-10 08:40:38
- nbrewer
- Novice
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
Since I know the coordinates of all circles, I wonder if I could imagine the points as a polygon. Not a polygon in the traditional sense, but the algorithm to find the center of a polygon (centroid) may still work. Or do you think the intersecting lines would cause the algorithm to fail?
The more I think about it, the more I think it would fail due to the vaarying radius sizes....
Last edited by nbrewer (2005-11-10 08:41:46)
#10 2005-11-10 08:46:05
- mathsyperson
- Moderator
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
What are you using to make all of those pictures? If other people could use it too, they might be able to play around with it to help them to help you.
Why did the vector cross the road?
It wanted to be normal.
#11 2005-11-10 09:11:27
- nbrewer
- Novice
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
It's actually all done in MS Excel. I then take a screen capture and manipulate the image in Photoshop. The code is spaghetti and not commented (alpha version), and it's not currently working very well, but I'll gladly share it with anyone. You can find it here:
http://www.bruware.com/cp/Circles.zip
After I get the kinks out, I plan on transferring the code to VB.NET. If I ever get around to it, I'll distribute the code and executable.
To use the Excel version (Assuming you have MS Excel installed):
1) Open sheet 1, and delete all the coordinates you see.
2) For as many circles as you want to play with, put in dummy coordinates. For example, if you want to play with 5 circles, put '1' in for the x and y of all circles radius 1-5.
3) Double click on 'Draw Circles'
4) Use your mouse and drag the circles around and place anywhere you like.
5) Once you have them positioned appropriately, click on 'Save Coordinates' (or something like that)
6) Then click on 'Draw Circles' again. You may have to click it several times to get the container circle to shrink down appropriately.
That's it. Cheesy, but a fun experiment.
#12 2005-11-11 01:25:53
- nbrewer
- Novice
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
Ah ha.....
http://www.laria.u-picardie.fr/~cli/CP03Paper41.pdf
Last edited by nbrewer (2005-11-11 01:26:33)
#13 2005-11-11 07:55:37
- MathsIsFun
- Administrator
Offline
Re: Finding the container circle of multiple circles (A circle packing Q)
Well found. And the authors say "No significant published research appears to exist addressing this problem, except ..."
Is this an NP-Complete (travelling salesman) type problem? (In other words, you really need to check all possibilities, and that can take unrealistic amounts of computer time)
My (limited) experience with such problems has been that just when you think you have the ultimate answer, someone comes along and shaves .002% off.
In which case, it deserves further work!
(BTW: It would be fun and educational to see the solutions animated)
"The physicists defer only to mathematicians, and the mathematicians defer only to God ..." - Leon M. Lederman
Pages: 1