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

1 AnswersA 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

0 Asked on November 3, 2021 by marco-farinati

1 Asked on November 3, 2021 by rodrigo-dias

fa functional analysis fredholm operators index theory kt k theory and homology vector bundles

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

ac commutative algebra ag algebraic geometry dedekind domains nonnoetherian valuation rings

0 Asked on November 3, 2021 by fisura-filozofica

0 Asked on November 3, 2021 by seva

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

at algebraic topology classifying spaces homotopy theory semigroups and monoids

0 Asked on November 3, 2021

analytic number theory co combinatorics generating functions

0 Asked on November 3, 2021

ag algebraic geometry geometric invariant theory orbifolds reference request reflection groups

1 Asked on November 3, 2021

limits and convergence measure theory stochastic calculus stochastic processes

0 Asked on November 3, 2021 by milo-moses

analytic continuation analytic number theory nt number theory

0 Asked on November 3, 2021

co combinatorics combinatorial optimization discrete geometry mg metric geometry permutations

0 Asked on November 3, 2021

0 Asked on November 3, 2021

differential operators elliptic pde heat equation linear pde mp mathematical physics

0 Asked on November 3, 2021

3 Asked on November 3, 2021 by tanya-vladi

fourier analysis fourier transform pr probability real analysis

9 Asked on November 3, 2021 by tom-leinster

0 Asked on November 3, 2021 by yemon-choi

2 Asked on November 3, 2021 by user175348

Get help from others!

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

Recent Answers

- eric_kernfeld on How to test consistency of responses?
- Philipp on How do i draw a ray in unity
- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- kjetil b halvorsen on How to test consistency of responses?
- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed

© 2022 AnswerBun.com. All rights reserved.