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.

Lesser

Squares have always the dimension two (2). You shouldn't use the word dimension in a mathematical context if you mean size or length. – Chemistry

Can the squares be rotated? That will complicate the algorithm significantly. – Sporocarp

"Programming language does not matter because this is more of a mathematical problem" → voted to close as off topic. Try asking on Math Stack Exchange. – Granado

Just because he mentioned that the language does not matter, I don't know if they necessarily means that it's off topic. What if the OP is just looking for pseudo code that he can interpret into his language of choice? – Holoenzyme

Of course that square can be rotated. – Lesser

@Holoenzyme It's off topic because it's a math problem belonging to math stack exchange not a programming problem. Your argument would make sense if they ONLY said the programming language does not matter but "because this is more of a math problem" is what tells us that this belongs on another site. – Hilton

Whether it's off topic here or not, I think he's very likely to get better answers at the math stackexchange site – Ungainly

Related web site: packomania.com – Outpatient

This is not as much a "math" problem as an "algorithm" problem. It's fair game on SO. Retagged accordingly. – Kinghorn

Answer 1

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%

Cadman

Answer 2

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.

Marxmarxian

I think it may be the case that, due to the symmetry of the problem, the only interesting subpixel cases are "even" and "odd" along each axis (center of circle at middle of square, or at edge of square), so you can just try all four. – Expellant

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.

Carnation

I think by "of some dimension" he meant, given a dimension D, how many squares of length D can ft into a circle of some radius R. – Holytide

I think High Performance Mark was perfectly aware of that and just did want to troll a little bit – Chemistry

@drhirsch Hm, would be a pretty silly troll to take fairly clearly worded question and pretend it's not. – Holytide

It wasn't that clearly worded before my edit, but the intent was clear – Chemistry

For non-aligned squares in a circle, have a look at www2.stetson.edu/~efriedma/squincir (esp. 28&34) – Pliant

Answer 4

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.

Holoenzyme

What if the answer requires the squares to exist on the diameter (as in the bisect of the square is the diameter) instead of along it? This solution doesn't take that into account. – Lunulate