# Reference: Packing under translation is in NP

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.

MathOverflow Asked by Till on November 26, 2021

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

Answered by Carlo Beenakker on November 26, 2021

## Related Questions

### Examples of “non equivalent” algebras that are derived equivalent?

0  Asked on November 3, 2021 by marco-farinati

### Equivalence of families indexes of Fredholm operators

1  Asked on November 3, 2021 by rodrigo-dias

### An example of a special $1$-dimensional non-Noetherian valuation domain

1  Asked on November 3, 2021 by s-t-stanly

### What are some interesting applications of the Archimedean Property?

0  Asked on November 3, 2021 by fisura-filozofica

### Origins of the “baby Freiman” theorem

0  Asked on November 3, 2021 by seva

### Is there a (discrete) monoid M injecting into its group completion G for which BM is not homotopy equivalent to BG?

0  Asked on November 3, 2021 by omar-antoln-camarena

### Unrestricting The Parameters of a Functional Equation

0  Asked on November 3, 2021

### Pseudoreflection groups in affine varieties

0  Asked on November 3, 2021

### Image of function contains identity elements

0  Asked on November 3, 2021 by pi66

### Integrate Radon-Nikodým derivatives against Lebesgue measure

1  Asked on November 3, 2021

### Higher derivatives of weighted zeta function and continuation to $s=1$

0  Asked on November 3, 2021 by milo-moses

### Distance properties of the permutations of a set of points in a Euclidean space

0  Asked on November 3, 2021

### Roots of determinant of matrix with polynomial entries — a generalization

0  Asked on November 3, 2021

### Laplacian coupled with another equation over a two-dimensional rectangular region

0  Asked on November 3, 2021

### Is there a finite equational basis for the join of the commutative and associative equations?

0  Asked on November 3, 2021

### What are some examples of proving that a thing exists by proving that the set of such things has positive measure?

9  Asked on November 3, 2021 by tom-leinster

### Literature and history for: lifting matrix units modulo various kinds of ideal

0  Asked on November 3, 2021 by yemon-choi

### Smallest family of subsets that generates the discrete topology

2  Asked on November 3, 2021 by user175348

### A global mathematics library

3  Asked on November 3, 2021