hide
Free keywords:
Computer Science, Computational Geometry, cs.CG,Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
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.
