I'm surprised there's no simple recursive way to find optimal (or at least good) answers. I would naturally assume the optimal way to pack n squares is to split them into groups of m and then pack each of those groups into k square subdivisions. Maybe the recursive patterns only show up at much larger n?
n centroids for the squares, n orientations (from 0 to pi/2) for the squares plus an orientation for the larger square means it can be reduced to finding minima of a 2n+1 degree polynomial.
