Skip to main content

All Questions

Filter by
Sorted by
Tagged with
13 votes
2 answers
664 views

Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason. Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$. I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
JSE's user avatar
  • 19.2k
4 votes
1 answer
204 views

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 ...
Till's user avatar
  • 479