polygon $P$ that can be placed into a simple polygon $Q$. Despite significant

effort, known algorithms require high polynomial running times. (Barequet and

Har-Peled, 2001) give a lower bound of $n^{2-o(1)}$ under the 3SUM conjecture

when $P$ and $Q$ are (convex) polygons with $\\Theta(n)$ vertices each. This

leaves open whether we can establish (1) hardness beyond quadratic time and (2)

any superlinear bound for constant-sized $P$ or $Q$.

In this paper, we affirmatively answer these questions under the $k$SUM

conjecture, proving natural hardness results that increase with each degree of

freedom (scaling, $x$-translation, $y$-translation, rotation): (1) Finding the

largest copy of $P$ that can be $x$-translated into $Q$ requires time

$n^{2-o(1)}$ under the 3SUM conjecture. (2) Finding the largest copy of $P$

that can be arbitrarily translated into $Q$ requires time $n^{2-o(1)}$ under

the 4SUM conjecture. (3) The above lower bounds are almost tight when one of

the polygons is of constant size: we obtain an $\\tilde O((pq)^{2.5})$-time

algorithm for orthogonal polygons $P,Q$ with $p$ and $q$ vertices,

respectively. (4) Finding the largest copy of $P$ that can be arbitrarily

rotated and translated into $Q$ requires time $n^{3-o(1)}$ under the 5SUM

conjecture.

We are not aware of any other such natural $($degree of freedom $+ 1)$-SUM

hardness for a geometric optimization problem.

},\n}\n'