I was looking at square packing problem which is defined as:

Given a number N... Find the smallest square that can pack N unit squares

Each square can be associated with a 3 dimensional point containing its x, y location and angle of orientation t.

For constraints we know the area of the enclosing hull can at most be the integer floor(sqrt(N))^2 and the minimal area is N itself

We can also write a system of constraints that make it so that none of the squares can overlap.

Finally our objective function for optimization is the area of the enclosing square of the set (is this easy to calculate?)

Can this formulation be used to efficiently solve the problem?

  • $\begingroup$ The area of the enclosing square is trivial to calculate since you can assume it is axis-aligned (your parameter space is general enough to enable this). Most packing problems are NP-complete so it is probably impossible to efficiently solve this problem. $\endgroup$ – Ron Kaminsky Jun 22 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.