I would probably reduce that rather complex problem to a one-dimensional problem first and extend it then to two dimension.

Try to find the longest intervals/ biggest free space on for example the x-axis using only item.pos_x+min_x/max_x (shouldn't be trivial) and (optionally?) sort them by length. Then do the same for the y-axis and somehow multiply all (big enough) spaces/ intervals with each of those on the other axis - or somehow like that, I cannot really imagine it right now in my head.