# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2111.02544.pdf

(Preprint), 2MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Künnemann, M., & Nusser, A. (2021). Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union. Retrieved from https://arxiv.org/abs/2111.02544.

Cite as: https://hdl.handle.net/21.11116/0000-0009-B462-D

##### 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.

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.