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)

]]>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.

]]>The more I think about it, the more I think it would fail due to the vaarying radius sizes....

]]>Thanks!

]]>Click "Post Reply", and you should see an "Upload Slots" selector. Have a go and tell me if it works for you.

]]>Example:

Yes... now you are seeing why this is tripping me up....

]]>[Each number represents 1 ÷ radius]

Even if it doesn't help, it's still cool!

]]>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.

]]>As you see, the container circle could be a bit smaller.

The circles go from radius 1 to radius 5.

And an image would help immensely. ]]>

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.

]]>