Calculating the maximum number of vertices in a packing problem

Question

I want to pack x number of pipes into a circle in two different formations; firstly in square formation, secondly in triangular formation.

It seemed obvious to reduce this to a packing problem, i.e. maximizing the amount of shapes that can be fitted onto a circle. With a "regular" formation, i.e. no vertices that coincident between two vertices on an edge or shapes that are rotated in any way:

For the first case, there's analytical estimations used for maximizing the amount of die on a silicon wafer, e.g.: $$DPW=\frac{\pi d^2}{4 S}-\frac{\pi d}{\sqrt{2 S}}$$

Is there a way of accurately approximating the total amount of vertices (my pipes) to the total number of squares? Secondly, can the same be done for a triangular pipe formation?

I've tried looking finding algorithms for MATLAB, but I was not able to find anything useful.

Answer 1

It seems you're confusing two different questions which are each interesting:

1. What's the greatest number of n congruent circles which can be packed into a circle of diameter d?

2. Given a square versus hexagonal packing of n congruent circles in the plane, what is the greatest number of circles enclosed by a circle of diameter d?

Neither of these seem to have an analytical solution for all d but have been found numerically for many values.

For the first question, you can see that the hexagonal packing is only optimal for n=3, the square packing is only optimal for n=4, and for larger n, the densest packings make regular polygonal patterns. Sorry I don't have privileges to post images.

For the second question, one needs to pick an origin in each of the square and hexagonally packed planes and then do a radial scan of all d/2 and count how many circles are fully enclosed in a diameter of d. The result depends on where one chooses the origin. It's scanning the plane of packed circles with a circular punch which can cut or leave intact some of the circles it captures, depending not only on the diameter of the punch but also where it strikes.

[1] http://mathworld.wolfram.com/CirclePacking.html

[2] http://www.packomania.com

Answer 2

Ken Stephenson has a trove of information on his website, and you may find his java app useful: http://www.math.utk.edu/~kens/CirclePack/