How many squares can be packed into a circle?

Question

How many squares of size a×a can be packed into a circle of radius R?

I don't need a solution. I just need some kind of a starting idea.

Answer 1

Just a shot in the dark after a few minutes of thought...

What if you worked with half the circle and doubled it at the end. I would start with a grid of squares the length of the diameter and the width of the radius, essentially blanketing the semi-circle. Then check all 4 corners of each square and make sure their coordinates are within the radius of the circle. This would of course require that you plot the circle and squares on some sort of coordinate system or grid.

I hope this makes sense... It's in my head and it seems a bit difficult to articulate :)

EDIT: After drawing it out, I think this method would work with a little tweaking. I would line up the squares along the diameter, but slide the first one down until it fits. Set that one in place and start lining up squares next to it until they no longer fit. Move out to the edge of this line of squares and repeat the same steps until your rows of squares reach the radius.

Answer 2

I apologise for writing such a long answer. My approach is to start with a theoretical maximum and a guaranteed minimum. When you approach the problem, you can use these values to determine how good any algorithm you use is. If you can think of a better minimum then you can use that instead.

We can define an upper limit for the problem by simply using the area of the circle

Upper Limit = floor( (PI * (r pow 2)) / (L * L) )

Where L is the width or height of the squares you are packing and r is the radius of the circle you are packing the squares into. We are sure this is an upper limit because a) we must have a discrete number of boxes and b) we cannot take up more space than the area of the circle. (A formal proof would work somewhere along the lines of assume we had one more box than this, then the sum of the area of the boxes would be greater than the area of the circle).

So with an upper limit in hand, we can now take any solution that exists for all circles and call it a minimum solution.

So, let's consider a solution that exists for all circles by taking a look at the largest square we can fit inside the circle.

The largest square you can fit inside the circle has 4 points on the perimiter, and has a width and length of sqrt(2) * radius (by using pythagoras' theorem and using the radius for the length of the shorter edges)

So the first thing we note is that if sqrt(2) * radius is less than the dimension of your squares, then you cannot fit any squares in the circle, because afterall, this is the largest square you can fit.

Now we can do a straightforward computation to divide this large square into a regular grid of squares using the L you specified, which will give us at least one solution to the problem. So you have a grid of sqaures inside this maximum square. The number of squares you can fit into one row of this this grid is

floor((sqrt(2) * radius)/ L)

And so this minimum solution asserts that you can have at least

Lower Limit = floor((sqrt(2) * radius)/ L) pow 2

number of squares inside the circle.

So in case you got lost, all I did was take the largest square I could fit inside the circle and then pack as many squares as possible into a regular grid inside that, to give me at least one solution.

If you get an answer at 0 for this stage then you cannot fit any squares inside the circle.

Now armed with a theoreitical maximum and an absolute minimum, you can start trying any sort of heuristic algorithm you like for packing squares. A simple algorithm would be to just split the circle up into rows and fit as many sqaures as you can into each row. You can then take this minimum as a guideline to ensure that you came up with a better solution. If you want to spend more processing power looking for a better solution, you use the theoretical as a guideline for how close you are to the theoretical best.

And if you care about this, you could work out what the maximum and minimum theoretical percentage of cover the minimum algorithm I idenfied gives you. The largest square always covers a fixed ratio (pi/4 or about 78.5% of the internal area of the circle I think). So the maximum theoretical minimum is 78.5% cover. And the minimum non-trivial (ie. non zero) theoretical minimum is when you can only fit 1 square inside the largest square, which happens when the squares you are packing are 1 larger than half the width and height of the largest square you can fit in the circle. Basically you take up just over 25% of the inner square with 1 packed square, which means you get an approximate cover of about 20%

Answer 3

You can pack as many squares as you like into a circle. If you doubt this statement, draw a large circle on a piece of paper, then draw a square with side length 10^(-18)m inside it, repeat. When you get near to the boundary of the circle, start drawing squares with side length of 10^(-21)m.

So your first step must be to refine your question and state your problem more accurately.

Answer 4

Rasterise the circle using something like the midpoint circle algorithm. The number of filled pixels is the number of squares you can fit in the circle. Of course, since you're not actually filling the pixels, just counting them, this should take time proportional to the circumference of the circle, not its area.

You'll have to pick the radius for rasterisation carefully, so that you only count pixels that are strictly inside the circle.

Edit: This may not be exactly correct, as it's possible that applying a sub-pixel offset to the grid could change the result. I'll leave the answer here as it may provide a useful starting point for an exact solution.