4
$\begingroup$

I am looking for a reference for a result that I am aware of. Let me describe the result.

Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP time, if $p_1,\ldots,p_n$ can be placed under translation into $C$.

The NP-algorithm goes as follows. guess for each pair of one line segment and one vertex their combinatorics. In other words, Is the point above or below the line spanned by the segment. Build a Linear program (LP) to check if all of those constraints can be met. Here the LP has $2n$ variables (two for each translation vector for each $p_i$) and each constraint is linear with up to four variables.

Note that one cannot just guess the coordinates, as we do not know a priori, they have polynomially bounded number of precision required.

I know the result from my PHD advisor Günter Rote, but I could not find a reference for this result.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

A proof that packing under translation of rectangles is NP-complete is given by Richard Korf, Optimal Rectangle Packing: Initial Results. See also this talk by Helmut Alt (search for "PAR is NP-complete"). It follows that polygon packing is NP-hard, but NP-completeness has no been proven in general, as far as I am aware. One special case is proven in Packing 2×2 unit squares into grid polygons is NP-complete

Improve this answer
$\endgroup$
1
  • $\begingroup$ The result by Richard Korf does not really address NP-membership. It just says "it is easy". Lecture Notes by Helmut Alt are not a citable source. Packing something onto a rid is indeed easily shown to be in NP, as there are only polynomially many possibilities. $\endgroup$
    – Till
    Commented Nov 22, 2019 at 12:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .