0
$\begingroup$

I've been learning about NP-Complete problems, and came across the rectangle fit problem. Basically, the rectangle-fit problem is the problem of whether or not a set of 2d rectangles can fit in a larger 2d rectangle. What I have not been able to find, or solve myself, is what a possible solution looks like.

Say there is a set of rectangles $R$ and a large rectangle $T$, how do I indicate a possible placement of all rectangles in $R$ into $T$? I was thinking coordinates, but there is no assumption $T$ is defined as a graph. At a high level, how would I denote where/how each rectangle should be placed?

I am not asking for how to solve this NP-Complete problem. I am asking how do I define the placement of rectangles in $R$ for a candidate solution. I saw an academic paper saying that it is obvious there is a polynomial time verifier for the problem, but there was no explanation of what the certificate the verifier is using looks like.

Particularly, I was looking at: http://ranger.uta.edu/~weems/NOTES5311/hw3ansold.pdf for the verifier.

$\endgroup$
1
$\begingroup$

You can simply list the coordinates of the upper-left corner of each rectangle (and its orientation, if you're allowed to rotate rectangles). That completely determines its position, and thus listing that for all rectangles completely identifies the configuration of all rectangles.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.