# Calculating the maximum number of vertices in a packing problem

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.

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.

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/