circlescombinatoricspacking-problem
Say you have an area, let's use a circle, and you want to cover it with circular objects (coins for example). How many coins can fit completely into this area without overlaps or deformation the coins. All the coins are the same size.
I've noticed there are two ways for the coins to tessellate:
in a triangular pattern where coins are placed with their centers at the vertices of a triangle. Like:
As has been mentioned over at SO, this problem is very difficult from a computational perspective. It may help to see what methods have been implemented for the packing problem. There are some algorithms out there, but you may have to fine-tune one to fit your needs.
Even a naive, greedy approach may end up being pretty inefficient. Would you take into account things like rotating the shape? There are all kinds of trade-offs to be made, but your "slices" (first fit) approach may work if you need something quick and dirty.
I think this question becomes much easier if we can know the four intersection points. And we can do this through observing the equilateral triangles if we join lines between centers of the circles.
If my calculation right, C $(\frac{\sqrt3}{2}r,\frac{1}{2}r)$, B $(\frac{1}{2}r,\frac{\sqrt3}{2}r)$, and you can work out the leftmost and downmost ones because of symmetry about the center $(\frac{1}{2}r,\frac{1}{2}r)$ but not even necessary.
One fourth of the area (suppose the upperright quarter) can be represented as:
$$\frac{S}{4} = \pi r^2\times\frac{30}{360}-\frac{(\frac{\sqrt3}{2}r-\frac{1}{2}r)\frac{1}{2}r}{2}\times 2$$
Simplified:
$$S=\frac{\pi}{3}r^2-(\sqrt3-1)r^2$$
Graph and the hilarious font :)
Look! This is integration-free!
Best Answer
The keyword of this subject is "circle packing". See for instance https://en.m.wikipedia.org/wiki/Circle_packing.
The hexagonal packing is the densest possible.