Max square size for unknown number inside rectangle

math tiles max-size
kenneth picture kenneth · May 15, 2009 · Viewed 14.8k times · Source

If I have a set of tiles (squares) which can be any number and they are to fill a container (rectangle) of an unknown size how do I work out the maximum size of the tiles without having any of them overlap.

So if I have 2 tiles and the rectangle is 100 * 100 then the max tile size is 50 * 50. This would also be the max size of tile if there was 3 or 4 tiles for this size of rectanlgle, which just so happens to be a square in this example.

If the rectanlge was 100 * 30 and I had 2 tiles, the max size of the square would be 30 * 30, if I have 4 tiles the max size would be 25 * 25.

How can I do this programatically without hogging the processor by going through every possible combination.

I try to summarise a bit better, I have a:

rectangle/bounding box that I need to fill as much as possible without the tiles overlapping.

I know the height and width of the rectangle (but this can change during runtime).

I have X number of tiles (this can change at run time), these are squares.

None of the tiles should overlap, what is the maximum size that each tile can be. They are all to be the same size.

Answer

Eric Bainville picture Eric Bainville · May 15, 2009

This is a packing problem. Optimal solutions are hard to find. See for example Packing N squares in a square.

You can compute an (optimistic) upper bound by dividing the total surface by the number of squares: sqrt(width*height/n).

Related questions

How can I check for NaN values?

float('nan') results in Nan (not a number). But how do I check for it? Should be very easy, but I cannot find it.

Read More
Math.random() explanation

This is a pretty simple Java (though probably applicable to all programming) question: Math.random() returns a number between zero and one. If I want to return an integer between zero and hundred, I would do: (int) Math.floor(Math.…

Read More
Calculate distance between two latitude-longitude points? (Haversine formula)

How do I calculate the distance between two points specified by latitude and longitude? For clarification, I'd like the distance in kilometers; the points use the WGS84 system and I'd like to understand the relative accuracies of the approaches available.

Read More