How many squares can I pack in a circle?

Question

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

I do not need a solution. I just need some kind of starting idea.

Answer 1

I apologize for writing such a long answer. My approach is to start with a theoretical maximum and a guaranteed minimum. When you approach a problem, you can use these values ​​to determine how good any algorithm you use is. If you can come up with a better minimum, you can use this instead.

We can define the upper limit for the task simply by 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 in which you are packing the squares. We are sure that this is the upper limit, because: a) we must have a discrete number of boxes and b) we cannot occupy more space than the area of ​​a circle. (The formal proof will work somewhere along the lines, assuming that we have one more box than this, then the sum of the boxes will be larger than the circle area).

So, having an upper limit in our hands, we can now make any decision that exists for all circles, and call it the minimum solution.

So, consider the solution that exists for all circles, looking at the largest square that we can place inside the circle.

The largest square that you can put inside the circle has 4 points on the perimeter and has the width and length sqrt(2) * radius (using the Pythagorean theorem and using the radius for the length of the shorter edges)

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

Now we can do a simple calculation to divide this large square into a regular grid of squares using the L you specify, 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 put on one line of this grid,

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

And so this minimal solution claims that you can have at least

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

the number of squares inside the circle.

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

If you get an answer of 0 for this stage, you cannot fit in the squares inside the circle.

Now, armed with a theoretical maximum and an absolute minimum, you can start using any heuristic algorithm that you like for packing squares. A simple algorithm would be to simply divide the circle into lines and place as many squares as you can on each line. You can then take this minimum as a guideline to make sure you come up with a better solution. If you want to spend more computing power to find a better solution, you use a theoretical justification of how close you are to theoretical.

And if you're interested, you can decide what maximum and minimum theoretical percent coverage of the minimum algorithm I idenfied gives you. The largest area always covers a fixed ratio (pi / 4 or about 78.5% of the inner area of ​​the circle, which I think). Thus, the maximum theoretical minimum is 78.5%. And the minimum non-trivial (i.e. Non-Zero) theoretical minimum is when you can only put 1 square in the largest square, which happens when the squares you are packing are 1 more than half the width and height of the largest square, you can fit in a circle. Mostly you occupy just over 25% of the internal area with 1 packed square, which means that you get an approximate cover of about 20%

Answer 2

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

So, your first step should be to clarify your question and more accurately identify your problem.

Answer 3

Rasterize a circle using something like a circle circumference algorithm . The number of filled pixels is the number of squares you can put in a circle. Of course, since you are not really filling the pixels, just counting them, this should take time proportional to the circumference of the circle, not its area.

You will need to select the radius to rasterize carefully, so that you will only count pixels that are strictly inside the circle.

Edit: this may not be entirely correct, since it is possible that applying a subpixel offset to the grid can change the result. I will leave the answer here, as it can be a useful starting point for an exact solution.

Answer 4

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

What to do if you worked with half a circle and doubled it at the end. I would start with a grid of squares of the length of the diameter and the width of the radius, essentially covering the semicircle. Then check all 4 corners of each square and make sure that their coordinates are in the radius of the circle. Of course, this will require that you build a circle and squares on some kind of coordinate system or grid.

Hope this makes sense ... It's in my head and it seems a little difficult to formulate :)

EDIT: Having pulled it out, I think this method will work with a little tweaking. I would have aligned the squares along the diameter, but moved the first one until it fits. Put it in place and start building squares next to it until they fit. Move to the edge of this line of squares and repeat the same steps until your rows of squares reach a radius.