@online{Kuennemann_2111.02544,
TITLE = {Polygon Placement Revisited: (Degree of Freedom + 1)-{SUM} Hardness and an Improvement via Offline Dynamic Rectangle Union},
AUTHOR = {K{\"u}nnemann, Marvin and Nusser, Andr{\'e}},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2111.02544},
EPRINT = {2111.02544},
EPRINTTYPE = {arXiv},
YEAR = {2021},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We revisit the classical problem of determining the largest copy of a simple 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.},
}