Algorithm needed for distributing rectangles evenly within another rectangle

Question

I am looking for an algorithm that can help distribute different sized rectangles within a larger rectangle while minimizing overlapping.

I have looked at bin packing algorithms, but they seem to minimize the amount of space between rectangles (in my case the all of the items being packed will be squares).

I guess I want to maximize the distance between all squares and the border of the outer rectangle.

Here is an example of what I am trying to do:

Anthemion

"minimizing overlapping", that implies they can overlap? – Abaxial

I guess you want to maximize the minimum distance between the squares and the border of the outer rectangle. – Swarts

@Abaxial I am not very worried if there is some overlap. I assumed there might be an algorithm that will work but can't handle variable size squares. In which case I would optimize for the median or average size. – Anthemion

@Swarts Yes I think that is what I am trying to do. "Maximize the minimum" distance between each square and the border of the outer rectangle – Anthemion

I like the question and would love to see some alternate approaches to this. @howardr, do you have a use case in mind for such a distribution? – Trocar

@Trocar the use case is for a project at work. We are displaying a bunch of celebrity photos in a large area. The size of the photo depends on the amount of recent twitter references about the celebrity. Basically we want to make sure the images don't overlap. As the photos change sizes we want to rearrange the photos in the workspace. – Anthemion

Answer 1

What if you packed them as tightly as possible, using an algorithm like the one described here, then expanded evenly to match the target enclosing rectangle?

For example, say you can pack the 3 rectangles above into a 3x2 box, and your outer box is 7x5. Then take the vector from the center of the box to the center to each rectangle, and multiply the x component by (7/3), and the y component by (5/2), and that gives the new center.

Jevon

Answer 2

This seems to be a generalization of the Knapsack Problem.

Dynamic programming will solve it in close to polynomial time.

Semimonthly

I looked at Knapsack problem before posting, and I think some of the algorithms related the solving it would work. I guess I don't know what variables to optimize for my main requirement which is to evenly distribute the squares within the outer rectangle (I apologize for my lay terms in describing my problem). – Anthemion