I have a couple of rectangles (~10'000 - 1'000'000) with various integer dimensions where each side is something between 1-10

I got to arrange these (without rotating) into a block of fixed width while minimizing height of the block (doesn't need to be the absolute minimum)

Additionally each rectangle is assigned a coordinate into some 2d vector space, and the packing algorithm should try to keep rectangles that are close-by each other in that vector space also more or less close-by each other in the packing (this in order to improve cache coherency)

Runtime performance of the algorithm is not very important.

Which algorithm is suitable for this problem?

  • 1
    $\begingroup$ I suspect this will be NP-hard. I suggest you investigate standard methods of dealing with NP-completeness. Also, you've listed two separate objectives ("minimize height" and "keep rectangles close by each other"), with no formalization of how to trade off between the two, so it isn't a precisely formalized problem statement yet. $\endgroup$
    – D.W.
    Aug 16 '21 at 4:33

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.