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

Marvin Künnemann ETH Zürich, Institute for Theoretical Studies. Research
supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich
Foundation. André Nusser Max Planck Institute for Informatics and Saarbrücken
Graduate School of Computer Science, Saarland Informatics Campus.

###### Abstract

We revisit a classical problem in computational geometry: Determine the
largest copy of a simple polygon $P$ that can be placed into the simple
polygon $Q$. Despite significant effort studying a number of settings, known
algorithms require high polynomial running times, even for the interesting
case when either $P$ or $Q$ have constant size. (Barequet and Har-Peled, 2001)
give a conditional 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 higher-order
$k$SUM conjecture, proving natural hardness results that increase with each
degree of freedom (scaling, $x$-translation, $y$-translation, rotation):

  * •

_(scaling, $x$-translation:)_ Finding the largest copy of $P$ that can be
$x$-translated into $Q$ requires time $n^{2-o(1)}$ under the 3SUM conjecture,
even for orthogonal (rectilinear) polygons $P,Q$ with $O(1)$ and $n$ vertices,
respectively.

  * •

_(scaling, $x$-translation, $y$-translation:)_ Finding the largest copy of $P$
that can be arbitrarily translated into $Q$ requires time $n^{2-o(1)}$ under
the 4SUM conjecture, even for orthogonal polygons $P,Q$ with $O(1)$ and $n$
vertices, respectively. This establishes the same lower bound under the
assumption that Subset Sum cannot be solved in time $O((2-\varepsilon)^{n/2})$
for any $\varepsilon>0$.

  * •

The above lower bounds are almost tight when one of the polygons is of
constant size: Using an offline dynamic algorithm for maintaining the area of
a union of rectangles due to Overmars and Yap, we obtain an $\tilde{\cal
O}((pq)^{2.5})$-time algorithm for orthogonal polygons $P,Q$ with $p$ and $q$
vertices, respectively. This matches the lower bounds up to an
$n^{1/2+o(1)}$-factor when $P,Q$ have $O(1)$ and $n$ vertices.

  * •

_(scaling, $x$-translation, $y$-translation, rotation:)_ Finally, 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.

As in our reductions, each degree of freedom determines one summand in a
$k$SUM instance, these lower bounds appear likely to be best possible under
$k$SUM. We are not aware of any other such natural $(\text{degree of
freedom}+1)$-SUM hardness for a geometric optimization problem. Finally, we
prove an additional tight OV hardness of the translations-only case.

##  1 Introduction

Consider the following basic question about two given simple polygons $P$ and
$Q$: What is the largest similar copy of $P$ that can be placed into $Q$ using
translation and rotation? Besides its appeal as a natural geometric
optimization problem, variants of this question occur in applications in
manufacturing (e.g., cutting the largest possible version of a given shape in
a given polygonal environment), motion planning (e.g., finding a _high-
clearance_ path for an object, i.e., a path with largest-possible spacing
between object and obstacles) and others. As an algorithmic optimization task
involving several geometric degrees of freedom (scaling, translation in two
dimensions, and rotation), it has led to a rich landscape of algorithmic works
on a variety of settings, including (but not limited to) [For85, LS87, CK93,
ST94, AAS98, AAS99].

Among the various studied settings, we have restrictions of the degrees of
freedom (such as a _fixed-size_ $P$ – i.e., no scaling – or no rotation),
convexity restrictions ($P$ or $Q$ are convex), or restrictions of the shape
(such as _orthogonal_ – i.e., rectilinear – polygons). In particular, the
fixed-size setting (with or without rotation) has been heavily studied both
for general $P$ and $Q$ [Cha83, AB89], for convex $P$ or convex $Q$ [Cha83,
AB89, ST94], for orthogonal $P$ and $Q$ [Her96], or for orthogonally convex
$P$ and $Q$ [BFM86]. For obtaining the largest scaling when $P$ is convex,
[For85] and [LS87] study the case without rotation, while [CK93, ST94, AAS98,
AAS99] take rotation into account. Note that when $P$ is convex, then the
existence of a placement of a $\lambda$-scaled copy of $P$ into $Q$ is a
monotone property in $\lambda$, and parametric search techniques can be used
(see [ST94] for a thorough discussion). For an additional overview, see
[OST17], [AS98].

Barely any of these results have near-linear running time, yet they stand for
more than two decades: When $P$ is convex, the current state of the art for
randomized algorithms is $\tilde{\cal O}(p^{2}q^{2})$ due to Agarwal, Amenta,
and Sharir [AAS99] where $p$ and $q$ denote the number of vertices of $P$ and
$Q$, respectively.111Throughout this paper $\tilde{\cal O}(T)={\cal
O}(T\mathrm{polylog}(T))$ is used to hide polylogarithmic factors. When $Q$ is
convex as well, this running time can be improved to $\tilde{\cal O}(pq^{2})$
[AAS98]. Note that these running times are not close to linear even for the
natural special case of $P$ being a small pattern polygon of constant size
$p={\cal O}(1)$. Even the fixed-size case (no scaling) for simple $P$ and $Q$
is challenging, with a current time bound of $\tilde{\cal O}(p^{3}q^{3})$. Are
such high polynomial running times really necessary, and if so, why?

A common type of evidence would be to give corresponding lower bounds on the
arrangement size encountered in their algorithmic solutions. Indeed, for
simple $P$ and $Q$ it is known that the Minkowski sum $P\oplus Q=\\{x+y\mid
x\in P,y\in Q\\}$ has size $\Theta(p^{2}q^{2})$ in the worst case (see
[AFH02]). However, it is not clear that constructing the full arrangement is
always necessary, and indeed Hernandez-Barrera [Her96] describes an
$\tilde{\cal O}(pq)$ algorithm for the fixed-size case without rotations for
_orthogonal_ $P$ and $Q$, avoiding a full construction. A similar case where a
supposed arrangement lower bound was broken is for the Hausdorff distance
under translation in $L_{1}$ and $L_{\infty}$ [CK92].

This begs the question whether _conditional lower bounds_ from established
hardness assumptions can be given. Conditional lower bounds base their
hardness on well-known and well-studied problems, which resisted algorithmic
improvements despite significant efforts and are therefore conjectured not to
be solvable in a certain running time, see [VW18] for a recent survey. While
these bounds can potentially be broken, this would require surprising
breakthroughs (and even then, the obtained connections may reveal further
information, such as which algorithmic techniques are required for further
progress). The only conditional lower bounds for the problem at hand that we
are aware of are due to Barequet and Har-Peled [BH01] and they are based on
the 3SUM Hypothesis [GO95].222See Section 2 for a definition of the $k$SUM
problem and corresponding hardness assumptions. Specifically, Barequet and
Har-Peled show that any ${\cal O}(n^{2-\varepsilon})$-time algorithm for
translating an orthogonal polygon $P$ with ${\cal O}(n)$ vertices into an
orthogonal polygon $Q$ with ${\cal O}(n)$ vertices would refute the 3SUM
Hypothesis. This lower bound is then shown to hold also for translating and
rotating a _convex_ $P$ into a _convex_ $Q$. While these results give first
important insights into the complexity of the polygon placement problem,
several questions remain unanswered: How do the different degrees of freedom
affect the problems’ hardness? Can we establish (1) any superlinear bound for
$p={\cal O}(1)$ and (2) any hardness beyond $n^{2-o(1)}$? In this paper, we
answer the last two questions affirmatively, and show that each degree of
freedom (scaling, $x$-translation, $y$-translation and rotation) can be used
to obtain a stronger hardness result, based on the $k$SUM conjecture. We
complement these conditional lower bounds by an algorithmic result via offline
dynamic algorithms for maintaining the union of rectangles.

##### Further Related Work.

Obtaining conditional lower bounds for optimizing a geometric functional under
translations of the input has recently received increasing interest. The
complexity of the (discrete) Fréchet distance [AG95, EM94], a natural
similarity measure of geometric curves, has been analyzed in [BKN21]: No
algorithm can compute the discrete Fréchet distance under translations of
polygonal input curves with at most $n$ vertices in time ${\cal
O}(n^{4-\varepsilon})$ under the Strong Exponential Time Hypothesis (SETH), or
more precisely, the 4-OV Hypothesis. This lower bound matches a natural
arrangement size lower bound, indicating that constructing such a large
arrangement is inherent in the problem. Interestingly, the authors also give
an ${\cal O}(n^{4.667})$-time algorithm by devising an offline dynamic
algorithm for maintaining reachability in a grid graph. This theme of using
offline dynamic algorithms for geometric optimization under translations will
re-emerge in the present paper.

There has been notable algorithmic work for optimizing the Fréchet distance
subject to more general transformations: Wenk [Wen02] proves that we can
optimize the Fréchet distance over a class of of transformation with $d$
degrees of freedom in time ${\cal O}(n^{3d+2})$. To the best of our knowledge,
no conditional lower bounds are known that prove a corresponding conditional
hardness parameterized by the degrees of freedom. For minimizing the Hausdorff
distance under translations, [BH01] give 3SUM-based lower bounds for segments,
and [BN21] give 3SUM- and OV-based lower bounds for point sets. Finally,
motion planning problems related to polygon placement, such as moving a line
segments through a given set of obstacles, are proven 3SUM-hard by Gajentaan
and Overmars [GO95]. Lower Bounds under $k$SUM for $k>3$ are much less
prevalent than 3SUM lower bounds: Such lower bounds have been given, e.g., for
problems related to convex hulls in $\mathbb{R}^{d}$ [Eri99], exact subgraph
finding [AL13], compressed string matching [ABBK17] and compressed linear
algebra [ABBK20].

###  1.1 Our Results and Technical Overview

To state our results, we first give an intuitive definition of $k$SUM and
Orthogonal Vectors (OV), see Section 2 for details. In the $k$SUM problem, we
are given $k$ sets of $n$ integers, and we ask whether there are $k$ integers
— one from each set — that sum to zero. This problem is hypothesized not to be
solvable in time ${\cal O}(n^{\lceil k/2\rceil-\epsilon})$ for any
$\epsilon>0$. In the Orthogonal Vectors (OV) problem, we are given two sets of
$n$ vectors in $\\{0,1\\}^{d}$ and we ask whether there is a vector from the
first set that is orthogonal to a vector from the second set. This problem is
hypothesized to not be solvable in time ${\cal
O}(n^{2-\epsilon}\mathrm{poly}(d))$ for any $\epsilon>0$.

Throughout this section, let $p$ and $q$ denote the number of vertices of the
input polygons $P$ and $Q$, respectively. As a simple first result, we obtain
that fixed-size polygon placement under translations has a quadratic-time
hardness not only under the 3SUM Hypothesis (as shown in [BH01]), but also
under the OV Hypothesis which is well known to be implied by the Strong
Exponential Time Hypothesis [Wil05]. This lower bound also applies to
unbalanced cases of the problem, where $p$ and $q$ may differ significantly.

######  Theorem 1.1.

Assuming the OV Hypothesis, there is no ${\cal O}((pq)^{1-\varepsilon})$-time
algorithm for any $\varepsilon>0$ for finding an $x$-translation of an
orthogonal polygon $P$ that fits into an orthogonal polygon $Q$. This holds
even restricted to $p=\Theta(q^{\alpha})$ for an arbitrary $\alpha>0$.

This lower bound tightly matches a corresponding ${\cal O}(pq\log(pq))$-time
algorithm for orthogonal polygons $P$ and $Q$ due to Hernandez-Barrera
[Her96]. Besides yielding a lower bound of $(pq)^{1-o(1)}$ for every
relationship between $p$ and $q$, this also immediately proves the same
hardness when we allow _any polynomial-space_ preprocessing of $P$ (or $Q$) by
a recent result [AVW21]. In the remainder of this section, we turn to the
cases where scaling is allowed. We first give a surprisingly simple 3SUM lower
bound for translations in a single dimension and scaling.

######  Theorem 1.2.

Assuming the 3SUM Hypothesis, there is no ${\cal O}(q^{2-\varepsilon})$-time
algorithm for any $\varepsilon>0$ for finding a largest copy of an orthogonal
$P$ that can be $x$-translated to fit into an orthogonal $Q$, even when
$p={\cal O}(1)$.

Specifically, we give quadratic-time hardness already when $P$ consists of a
small number of $p=12$ vertices. Technically, this result is achieved by a
surprisingly simple reduction from the Average problem, which is defined as
follows. Given a set $A$ of $n$ integers in $\\{-U,\dots,U\\}$ with $U=n^{3}$,
determine whether there are $a_{1},a_{2},a_{3}\in A$ such that
$a_{2}-a_{1}=a_{3}-a_{2}$. Only recently, Dudek, Gawrychowski, and
Starikovskaya [DGS20] could prove 3SUM-hardness of this problem, resolving an
open problem posed by Erickson.333As we shall see below, it is not strictly
necessary to reduce from Average, since we can reduce from 3SUM directly if we
exploit more of the geometric structure of the problem. However, reducing from
this problem produces the simplest and most intuitive construction. We reduce
from this problem by using a polygon $P$ that essentially consists of three
very long prongs, with an equal spacing of approximately 1 between them (see
the figure on the top right).

The corresponding polygon $Q$ is illustrated in the figure on the left: It
encodes the set $A$ of input integers in $\\{-U,\dots,U\\}$ by long attached
rectangles for each integer in $A$. The main idea is that we can place a
scaled version of $P$ into $Q$ if and only if we can translate the left prong
to be contained in a rectangle representing some $a_{1}\in A$, and choose a
scaling of $\lambda\approx a_{2}-a_{1}$ for some $a_{2}\in A_{2}$ (making sure
that the middle prong fits into the rectangle representing $a_{2}$) such that
there exists $a_{3}\in A$ with $a_{3}\approx a_{2}+\lambda\approx
2a_{2}-a_{1}$ (making sure that the right prong can be placed into the
rectangle representing $a_{3}$). In other words, the instance is equivalent to
the existence of $a_{1},a_{2},a_{3}\in A$ with $a_{2}-a_{1}=a_{3}-a_{2}$. We
give the details (including how to choose widths and lengths of the prongs,
etc.) in Section 4. There, we also show that even _approximating_ the largest
scaling factor by any polynomial factor suffers from the same hardness.

In the above lower bound, we only exploited scaling and $x$-translations to
obtain our hardness, but ignored the possibility of $y$-translations. Indeed,
taking into account this additional degree of freedom, we can obtain the same
hardness result based on the 4SUM Hypothesis.

######  Theorem 1.3.

Assuming the 4SUM Hypothesis, there is no ${\cal O}(q^{2-\varepsilon})$-time
algorithm for any $\varepsilon>0$ for finding a largest copy of an orthogonal
$P$ that can be $x$-translated to fit into an orthogonal $Q$, even when
$p={\cal O}(1)$.

It is well known that finding an ${\cal O}(n^{2-\varepsilon})$-time algorithm
for 4SUM would exponentially improve over the state-of-the-art meet-in-the-
middle running time of ${\cal O}(2^{n/2})$ for Subset Sum.444This result
follows by the split and list technique: Split the $n$ items into 4 parts of
$n/4$ items each. For each part, list the weight of each subset of items,
resulting in $4$ sets of at most $N=2^{n/4}$ numbers. If we could determine
whether there exists a tuple $a_{1},a_{2},a_{3},a_{4}$ with
$a_{1}+a_{2}+a_{3}+a_{4}=t$ in time ${\cal O}(N^{2-\varepsilon})$, we would
obtain an ${\cal O}(2^{N(1/2-\varepsilon/4)})$-time algorithm for Subset Sum.
Thus, the above lower bound also holds under the assumption that Subset Sum
admits no exponential improvement over the meet-in-the-middle running time
${\cal O}(2^{n/2})$. Note that from the 3SUM lower bound, we could only deduce
a $q^{1.5-o(1)}$ lower bound under the Subset Sum assumption.

Technically, the result can be achieved similarly to the 3SUM lower bound. The
first natural idea would be to design $P$ to have 2 horizontal and 2 vertical
prongs, each pair within distance approximately $1$, see the figure on the
right. It is intuitive that for $Q$, one can use the set gadget from the 3SUM
lower bound on the bottom, representing a set $A$, and a vertical copy of the
set gadget on the left, representing a set $B$, to encode the problem whether
there exist distinct $a_{1},a_{2}\in A$ and distinct $b_{1},b_{2}\in B$ such
that $a_{1}-a_{2}=b_{1}-b_{2}$. Curiously, even with the techniques of Dudek
et al. [DGS20], it is unclear whether one can show 4SUM-hardness of the
problem (the problem here is that not every summand is taken from a different
set, i.e., the input is not 4-partite). However, exploiting the full
generality of our geometric setting, we can circumvent this issue rather
easily.

In the figure on the left, we illustrate the polygon $P$ that we use to obtain
our result. It has two vertical prongs, one directed downwards, the other
directed upwards, with a horizontal distance of approximately $1$. Likewise,
we have a left horizontal and a right horizontal prong within vertical
distance of approximately $1$. We choose $Q$ to be essentially square-shaped,
with set gadgets on the bottom, left, top and right representing four input
sets $A_{1},B_{1},A_{2},B_{2}$, respectively. In this way, any placement of
$P$ in $Q$ chooses some $a_{1}\in A_{1},b_{1}\in B_{1}$ as the position for
the bottom and left prong, respectively. Note that the scaling factor
$\lambda$ must be approximately $a_{2}-a_{1}$ for some $a_{2}\in A_{2}$ so
that the top prong can be contained in a rectangle representing $a_{2}$. Since
$\lambda$ scales the distances of the horizontal and the vertical prongs
uniformly, this also determines the fourth remaining summand: there must be
some $b_{2}\in B_{2}$ such that $b_{2}-b_{1}\approx\lambda\approx
a_{2}-a_{1}$. Thus, there exists a (large) scaling of $P$ that can be placed
into $Q$ if and only if there are $a_{1}\in A_{1},a_{2}\in A_{2},b_{1}\in
B_{1},b_{2}\in B_{2}$ such that $a_{2}-a_{1}=b_{2}-b_{1}$. To simplify the
presentation, we defer the proof of the 4SUM lower bound to Section 6, _after_
the presentation of the 5SUM lower bound in Section 5.

##### Algorithmic Results and Tightness of Lower Bounds for Scaling and
Translation.

We show that our conditional lower bounds are not far from optimal for
orthogonal polygons when $p$ or $q$ are constant.555Note that we formally
prove hardness only for constant $p$. However, it is rather straightforward to
adapt the lower bounds to constant $q$, which we will do in the full version
of the paper. To this end, let $\lambda P$ denote the polygon $P$ scaled by
$\lambda$. It is not difficult to obtain an $\tilde{\cal O}((pq)^{3})$
baseline algorithm: We first observe that there is a set of at most ${\cal
O}((pq)^{2})$ _critical_ values that must contain the largest scaling factor
$\lambda^{*}$.666For readers’ convenience, we give an intuitive argument: Take
an optimal scaling $\lambda^{*}$ of $P$ and fix a corresponding placement of
$\lambda^{*}P$ into $Q$. Move the polygon to the left and to the bottom until
there is contact between horizontal segments $e_{P},e_{Q}$ of $\lambda^{*}P$
and $Q$ as well as vertical segments $f_{P},f_{Q}$ of $\lambda^{*}P$ and $Q$.
The claim is that there exists an additional pair of horizontal or vertical
segments $g_{P},g_{Q}$ of $\lambda^{*}P$ and $Q$ that have a contact.
Otherwise, we could use a larger scaling factor $\lambda^{\prime}>\lambda^{*}$
and still be able to place $\lambda^{\prime}P$ into $Q$. Now, if $g_{P},g_{Q}$
are horizontal segments, then the contacts of $e_{P},e_{Q}$, and $g_{P},g_{Q}$
uniquely determine $\lambda^{*}$, otherwise the contacts of $f_{P},f_{Q}$ and
$g_{P},g_{Q}$ uniquely determine $\lambda^{*}$. Thus, there are at most
$2(pq)^{2}$ possible scalings, given by horizontal or vertical contacts. For
each such critical scaling factor $\lambda$, we can determine whether $\lambda
P$ can be translated into $Q$ in time ${\cal O}(pq\log(pq))$ by [Her96]. At
this level of abstraction, this algorithm cannot be improved: Even with a
fixed $Q$ with $q$ vertices, testing for a list of $L$ polygons
$P_{1},\dots,P_{L}$ with $p$ vertices whether $P_{i}$ can be translated to be
contained in $Q$ can be proven to require time $(Lpq)^{1-o(1)}$ under the OV
Hypothesis (via an adaptation of Theorem 1.1).

However, we can improve this algorithm significantly, yielding an $\tilde{\cal
O}(q^{2.5})$-time algorithm for constant $p$.

######  Theorem 1.4.

For polygons $P,Q$, let $\lambda^{*}$ denote the largest scaling factor
$\lambda$ such that $\lambda P$ can be placed into $Q$ under translations.
Given any orthogonal simple polygons $P$ and $Q$ with $p$ and $q$ vertices,
respectively, we can compute $\lambda^{*}$ in time ${\cal
O}((pq)^{2.5}2^{{\cal O}(\log^{*}pq)})$.

Interestingly, the above algorithm is obtained using an offline dynamic
algorithm for maintaining the union of $n$ rectangles in amortized
$\tilde{\cal O}(\sqrt{n})$ time, which led to algorithms for Klee’s measure
problem (see [OY91, Cha10]). The basic idea is to cover $P$ and
$\mathbb{R}^{2}\setminus Q$ by rectangles $P_{1},\dots,P_{p^{\prime}}$ and
$Q_{1},\dots,Q_{q^{\prime}}$, respectively, where $p^{\prime}={\cal O}(p)$ and
$q^{\prime}={\cal O}(q)$. Let $R_{i,j}$ denote the set of translations of $P$
such that $P_{i}$ intersects the interior of $Q_{j}$, yielding a set of
_forbidden_ translations (under such a translation, some part of $P$ lies
outside of $Q$). Note that the $R_{i,j}$ are rectangles as well. Consequently,
$P$ can be placed into $Q$ under translation $\tau$ if and only if $\tau$ is
not contained in any of the forbidden regions, i.e., it is not contained in
$\bigcup_{i,j}R_{i,j}$.

For a scaled copy $\lambda P$, we view the set of $R_{i,j}$’s as a dynamically
changing set of (open) rectangles, parameterized by the scaling factor
$\lambda$. While these rectangles may completely change with every change in
$\lambda$, we may find a suitable representation in rank space that incurs
only few, i.e., ${\cal O}((pq)^{2})$, combinatorial changes. More
specifically, we show how to reduce the problem of determining the largest
$\lambda$ such that $\bigcup_{i,j}R_{i,j}(\lambda)$ does not cover all
possible translations to the problem of determining the first point at which a
dynamically changing set of rectangles contains a hole, where updates are
specified in advance. Using a data structure with amortized $\tilde{\cal
O}(\sqrt{n})$-time updates, we obtain a $\tilde{\cal O}((pq)^{2.5})$-time
algorithm over all ${\cal O}((pq)^{2})$ updates. We give the proof in Section
7.

##### The Remaining Degree of Freedom: Rotation.

Finally, we take into account rotation as an additional degree of freedom.
Specifically, for the setting of scaling, translation, and rotation, we obtain
cubic-time hardness based on the 5SUM Hypothesis.

######  Theorem 1.5.

Assuming the 5SUM Hypothesis, there is no ${\cal
O}((p+q)^{3-\varepsilon})$-time algorithm for any $\varepsilon>0$ for finding
a largest copy of a simple polygon $P$ that can be rotated and translated to
fit into a simple polygon $Q$.

This result concludes our line of $(\text{degree of freedom}+1)$-SUM hardness
results for the problem. For each degree of freedom, we show how it can be
used to determine one summand in a corresponding $k$SUM instance, where the
remaining summand is uniquely determined by the previous choices. We are not
aware of any other geometric optimization problem for which such a natural
$(\text{degree of freedom}+1)$-SUM hardness is known.

The 5SUM lower bound of Theorem 1.5 is perhaps the most interesting technical
contribution of the paper. A natural approach to adapt the 4SUM construction
would be to arrange many rotated copies of the four prongs of $P$ into a
wheel-like structure (see the figure on the right). In such a construction,
the rotation can choose a group $i$ of four prongs to be tested against set
gadgets situated at the bottom, left, top, and right. Which information can we
encode into the choice of the group? A central idea of our approach is that,
instead of letting the prongs have a uniform distance of approximately 1, we
use different distances for the corresponding $x$\- and the $y$-directions,
say a distance of $1$ for the vertical prongs and a distance of $\mu_{i}$ for
the horizontal prongs. With such a construction, one might hope to reduce from
the following problem:

$\exists a_{1}\in A_{1},a_{2}\in A_{2},b_{1}\in B_{1},b_{2}\in B_{2},\mu\in
M:b_{2}-b_{1}=\mu(a_{2}-a_{1}).$

While this problem has a similar structure to 5SUM, it is unclear whether it
is indeed 5SUM-hard: the combination of additive and multiplicative structures
might make this problem simpler. It turns out, however, that we can reduce
from 5SUM into our geometric problem directly, by exploiting that our gadgets
can be made robust against small perturbations (we need to ensure a certain
robustness anyway to deal with slight possible variations of the desired
translations, scalings, and rotations, which poses a minor technical
complication in our proofs). More specifically, the idea is to use that, when
choosing $\mu=1+\varepsilon$ for small values of $\varepsilon$, we can
approximate $\mu(a_{2}-a_{1})=(1+\varepsilon)(a_{2}-a_{1})\approx
a_{2}-a_{1}+\varepsilon$. To exploit this trick, consider the following
(equivalent) formulation of 5SUM:

$\exists a_{1}\in A_{1},a_{2}\in A_{2},b_{1}\in B_{1},b_{2}\in B_{2},c\in
C:b_{2}-b_{1}=a_{2}-a_{1}+c,$

where $A_{1},A_{2},B_{1},B_{2},C$ are sets of $n$ integers in
$\\{-U,\dots,U\\}$ with $U=n^{5}$. The idea is to set
$\mu_{i}=1+\frac{c_{i}}{M}$ where $c_{i}$ is the $i$-th element in $C$ and $M$
is a large value to be determined later. We need to adapt the placement of the
set gadgets slightly: the bottom and top set gadgets, representing
$A_{1},A_{2}$, should be spaced at a horizontal distance of essentially $M$.
Likewise, we place the left and right set gadgets, representing $B_{1}$ and
$B_{2}$, at a vertical distance of essentially $M$. Intuitively, we can place
$\lambda P$ (for large enough $\lambda$) into $Q$ if and only if the following
conditions hold:

  * –

The rotation chooses a group and thus a corresponding factor
$\mu_{i}=1+\frac{c}{M}$ for some $c\in C$.

  * –

The $x$-translation chooses some $a_{1}\in A_{1}$ whose rectangle contains the
bottom prong of the chosen group.

  * –

The $y$-translation chooses some $b_{1}\in B_{1}$ whose rectangle contains the
left prong of the chosen group.

  * –

The scaling $\lambda$ is approximately equal to $M+a_{2}-a_{1}$ for some
$a_{2}\in A_{2}$ whose rectangle contains the top prong of the chosen group.

  * –

Finally, the right prong of the chosen group must be contained in the
rectangle of some $b_{2}\in B_{2}$ determined by
$M+b_{2}-b_{1}\approx\lambda\mu\approx(M+a_{2}-a_{1})(1+\frac{c}{M})=M+a_{2}-a_{1}+c+\frac{(a_{2}-a_{1})c}{M}$.
By choosing $M$ large enough (e.g., $M=U^{3}$) we can ensure that the
approximation error $\frac{(a_{2}-a_{1})c}{M}=o(1)$ is negligible. We obtain
equivalence with $b_{2}-b_{1}=a_{2}-a_{1}+c$.

In Section 5, we give the proof of the theorem, showing how to also overcome
further technical complications, such as possible deviations from the intended
translations, scalings, and rotations (e.g., we need to enforce that a
rotation is chosen that enforces prongs intended for $A_{1},A_{2}$ are not
rotated to intersect with $B_{1},B_{2}$).

##### Approximation Hardness.

It turns out that the above hardness results also give strong hardness of
approximation. We detail this for the case of scaling and x-translations in
Section 4. The same arguments can be used to obtain similar statements for our
other settings.

###  1.2 Outlook and Open Problems

We provide insights into the fine-grained complexity of the polygon placement
problem, by showing $(\text{degree of freedom}+1)$-SUM hardness. For the cases
without rotations and constant-size $P$, we show that the optimal running time
is between $q^{2-o(1)}$ (assuming the 4SUM Hypothesis) and $\tilde{\cal
O}(q^{2.5})$, by an improvement via offline dynamic algorithms. Can we close
this gap? We believe that an algorithmic improvement is more likely than a
higher lower bound.

Similar challenges remain for more general cases: Can we generalize some of
our algorithmic ideas for orthogonal polygons to general simple polygons? On
the hardness side, it is an interesting challenge to prove even higher, i.e.,
super-cubic, conditional lower bounds when $p=\Theta(q)$. However, proving
higher bounds from the $k$SUM Hypothesis appears rather unlikely, as in our
constructions, each degree of freedom naturally chooses a corresponding
summand in a given $k$SUM instance. Finally, can we use ideas from this paper
to give hardness also for convex $P$ and/or $Q$? Barequet and Har-Peled [BH01]
could adapt their lower bounds for the fixed-size case under translation to
convex $P$ and $Q$ in a quite natural way. It is unclear how this could be
done for our lower bounds, so that proving stronger lower bounds for convex
restrictions remains an interesting open problem.

##  2 Preliminaries

Before we can show our results, we introduce some notation, cleanly define the
problems at hand, and revisit some geometric facts that will come in handy in
our proofs.

###  2.1 Notation and Conventions

We let $[n]$ denote $\\{1,\dots,n\\}$. For any $x,y,\varepsilon\in\mathbb{R}$,
we use $x\in y+[-\varepsilon,\varepsilon]$ to denote
$x\in[y-\varepsilon,y+\varepsilon]$. We typically think of a placement of $P$
into $Q$ via a tuple $(\lambda,\tau,\alpha)$: we scale $P$ by the scaling
factor $\lambda>0$ (with respect to the center of $P$ as its reference point),
rotate it in counter-clockwise direction by the rotation angle
$\alpha\in(-\pi,\pi]$ (around the center of $P$) and translate the resulting
polygon by the translation vector $\tau\in\mathbb{R}^{2}$. To this end, let
$\lambda P$ denote the polygon $P$ scaled by $\lambda$.

###  2.2 Hardness Assumptions

In this work we use two standard hypotheses from fine-grained complexity
theory: the $k$SUM Hypothesis and the OV Hypothesis. Most of our lower bounds
are derived from the former.

####  $k$SUM.

For $k\geq 2$, let $k$SUM denote the following problem: Given sets
$A_{1},\dots,A_{k}$ of $n$ integers in $\\{-U,\dots,U\\}$ with $U=n^{k}$,
determine whether there exist $a_{1}\in A_{1},\dots,a_{k}\in A_{k}$ with
$\sum_{i=1}^{k}a_{i}=0$. This problem is well known to be solvable in time
${\cal O}(n^{\lceil k/2\rceil})$. The hypothesis that this running time cannot
be improved by a polynomial factor is known as the $k$SUM Hypothesis:

######  Hypothesis 2.1 ($k$SUM Hypothesis).

Let $k\geq 3$. For no $\epsilon>0$, there is an ${\cal O}(n^{\lceil
k/2\rceil-\epsilon})$-time algorithm for $k$SUM.

There is a vast literature of conditional lower bounds based on the 3SUM
conjecture, starting with [GO95] (see [VW18] for an overview). For lower
bounds from $k$SUM for $k>3$, we refer to [Eri99, AL13, ABBK17, ABBK20].

#### Orthogonal Vectors.

We also give a simple lower bound based on the Orthogonal Vectors (OV)
problem. In this problem, we are given two sets $A,B$ of vectors in
$\\{0,1\\}^{d}$, and the task is to determine whether there is a pair $a\in
A,b\in B$ that is orthogonal, i.e., for all $k\in[d]$ we have $a_{i}[k]\cdot
b_{j}[k]=0$. The obvious algorithm runs in time $O(|A||B|d)$, and is
conjectured to be best-possible up to subpolynomial improvements in $|A|,|B|$:

######  Hypothesis 2.2 (OV Hypothesis).

There is no $\varepsilon>0$ and $\alpha>0$ such that we can solve OV with
$|A|=\Theta(|B|^{\alpha})$ in time ${\cal
O}((|A|\cdot|B|)^{1-\varepsilon}\mathrm{poly}(d))$.

This hypothesis is typically stated for fixed $\alpha=1$, which is well-known
to be equivalent to the above formulation, see e.g. [BK15, Lemma II.1]. It is
well known that the OV Hypothesis is implied by the Strong Exponential Time
Hypothesis, see [Wil05, VW18].

###  2.3 Basic Geometric Facts

We exploit the following approximations of trigonometric functions.

######  Fact 2.1 (Small angle approximations).

For $0\leq\alpha\leq\frac{\pi}{4}$, we have

$\displaystyle\frac{2}{\pi}\alpha$ $\displaystyle\leq\sin(\alpha)\leq\alpha,$
$\displaystyle 1-\frac{\alpha^{2}}{2}$ $\displaystyle\leq\cos(\alpha)\leq 1,$
$\displaystyle\alpha$ $\displaystyle\leq\tan(\alpha)\leq\alpha+\alpha^{3}$

The basic shape of our polygons will be regular $4n$-gons, for which we
collect the following facts.

######  Lemma 2.1 (Regular $4n$-gon facts).

Let $a_{P}$ and $R_{P}$ denote the apothem and circumradius, respectively, of
a regular $4n$-gon $P$ of side length $s$. Then for sufficiently large $n$,

$\frac{sn}{2}\leq a_{P}\leq R_{P}\leq sn.$

###### Proof.

Note that by Fact 2.1,
$\tan(\frac{\pi}{4n})\leq\frac{\pi}{4n}+(\frac{\pi}{4n})^{3}\leq\frac{1}{n}$
for sufficiently large $n$. Thus,
$a_{P}=(s/2)\cdot(1/\tan(\frac{\pi}{4n}))\geq sn/2$. Furthermore, we have
$a_{P}\leq
R_{P}=(s/2)\cdot(1/\sin(\frac{\pi}{4n}))\leq(s/2)(\pi/2)(4n/\pi)=sn$. ∎

Finally, the following lemma enables us to conveniently analyze intersections
of the rotated polygon when we know its rotation up to a small additive error
in $[-\varepsilon,\varepsilon]$.

Figure 1: Intersection of a horizontal line with a vertical line at distance
$\Delta$, rotated by $\alpha$

######  Lemma 2.2 (Line Rotation Lemma).

Consider a vertical line $L_{P}$ at $x=\Delta$ and a horizontal line $L_{Q}$
at $0\leq y\leq Y$. Let $\Delta^{\prime}$ denote the $x$-coordinate at which
$L_{P}$, rotated around the origin by an angle
$\alpha\in[-\varepsilon,\varepsilon]$ with $\varepsilon\leq\pi/4$, intersects
$L_{Q}$. Then

$\Delta-Y\varepsilon\leq\Delta^{\prime}\leq\Delta(1+\varepsilon^{2})+Y\varepsilon.$

###### Proof.

As illustrated in Figure 1, the intersection of the rotated $L_{P}$ with
$L_{Q}$ is at the $\mathrm{x}$-coordinate $\Delta/\cos(\alpha)+y\sin(\alpha)$.
By Fact 2.1, we obtain

$\Delta/\cos(\alpha)+y\sin(\alpha)\geq\Delta-Y\varepsilon,$

as well as, using $(1-\alpha^{2}/2)^{-1}\leq 1+\alpha^{2}$ for $\alpha\leq 1$,

$\Delta/\cos(\alpha)+y\sin(\alpha)\leq\Delta(1-\alpha^{2}/2)^{-1}+Y\varepsilon\leq\Delta(1+\varepsilon^{2})+Y\varepsilon.$

∎

##  3 OV Lower Bound for Translation

In this section, we present the OV-based lower bound for the polygon placement
problem with translations only, i.e., we prove Theorem 1.1. Given
$A,B\subseteq\\{0,1\\}^{d}$, we construct $P$ and $Q$ as illustrated in
Figures 3 and 3, respectively. For the polygon $P$, we define $|A|$ vector
gadgets: the vector gadget for $a_{i}\in A$ has width $d$, and the $k$-th
width-$1$ section of the gadget has height $1+a_{i}[k]$. To obtain the full
polygon $P$, we concatenate the vector gadgets for $a_{1},\dots,a_{|A|}$,
separated by width-1, height-3 _separator_ rectangles (which we also prepend
to the left of $a_{1}$ and append to the right of $a_{|A|}$, see Figure 3. In
total, we obtain a polygon of width $W\coloneqq|A|(d+1)+1$ and height 3,
consisting of ${\cal O}(|A|d)$ vertices.

For the polygon $Q$, we define $|B|$ analogous vector gadgets: the vector
gadget for $b_{j}\in B$ has width $d$, and the $k$-th width-$1$ section of the
gadget has height $2-b_{j}[k]$. Again, we obtain the full polygon $Q$ by
concatenating the vector gadgets for $b_{1},\dots,b_{|B|}$, this time
separated by width-$\Delta$, height-3 separator rectangles with
$\Delta\coloneqq(|A|-1)(d+1)+1$, which we also prepend to the left of
$b_{1}$’s vector gadget and append to the right of $b_{|B|}$’s vector gadget.
This way, we obtain a polygon $Q$ with ${\cal O}(|B|d)$ vertices.

Figure 2: The polygon $P$ (blue) capturing a vector set
$A=\\{0100,0010,1100,0110\\}$.

Figure 3: The polygon $Q$ (green) capturing the vector set
$B=\\{0111,1100,0101\\}$. We also give a feasible placement of a polygon $P$
(blue) for a vector set $A=\\{0100,0010,0111,1001\\}$. Recall that
$\Delta=(|A|-1)(d+1)+1$.

######  Claim 3.1.

$P$ can be translated to be contained in $Q$ if and only if there are
$a_{i}\in A,b_{j}\in B$ that are orthogonal.

###### Proof.

Assume that there is an orthogonal pair $a_{i}\in A,b_{j}\in B$. Then we place
$P$ into $Q$ by having their bottom boundaries align and using the unique
$x$-translation that aligns the vector gadgets of $a_{i}$ and $b_{j}$ (see
Figure 3 for an example). The vector gadget of $a_{i}$ fits into the vector
gadget for $b_{j}$, since the $k$-th width-1 section of $a_{i}$’s vector
gadget has height $1+a_{i}[k]\leq 2-b_{j}[k]$ (as orthogonality of
$a_{i},b_{j}$ implies $a_{i}[k]+b_{j}[k]\leq 1$ for all $k$). Furthermore, the
part of $P$ that is to the left of $a_{i}$’s vector gadget has width
$(i-1)(d+1)+1\leq\Delta$ and height 3, and thus fits into the separator to the
left of $b_{j}$’s vector gadget. Likewise, the part of $P$ to the right of
$a_{i}$’s vector gadget fits into the separator to the right of $b_{j}$’s
vector gadget.

Conversely, consider any translation of $P$ that fits into $Q$. We claim that
it must perfectly align some vector gadget $a_{i}$ with some vector gadget
$b_{j}$: Since the leftmost and rightmost separator rectangle of $P$ have a
distance of $|A|(d+1)-1>\Delta$, these rectangles must be placed in two
different separator rectangles of $Q$. Fix $b_{j}$ to be the vector
represented between these two separator rectangles. Since this vector gadget
has height at most $2$, we must find, in this width-$d$ section, a
corresponding width-$d$ section of $P$ of height at most $2$, which can only
be the vector gadget for some $a_{i}$ (by the structure of $P$). Since the
vector gadget of $a_{i}$ must fit into the vector gadget for $b_{j}$, we
obtain from containment in the $k$-th width-$1$ section that $1+a_{i}[k]\leq
2-b_{j}[k]$. Since $a_{i}[k],b_{j}[k]\in\\{0,1\\}$, we obtain that
$a_{i}[k]\cdot b_{j}[k]=0$ for all $k$, proving that $a_{i}$ and $b_{j}$ are
orthogonal. ∎

From this reduction, a $(pq)^{1-o(1)}$ lower bound based on the OV Hypothesis
is immediate.

###### Proof of Theorem 1.1.

Assume for contradiction that there are $\varepsilon,\alpha>0$ such that we
can solve the polygon placement problem under translation for $Q$ and $P$ with
$q$ and $p=\Theta(q^{\alpha})$ vertices in time ${\cal
O}((pq)^{1-\varepsilon})$. Then, given any OV instance $A,B$ with
$|A|=\Theta(|B|^{\alpha})$, using the above reduction we can produce an
equivalent polygon placement problem instance $P$, $Q$ with
$p=\Theta(|A|\mathrm{poly}(d))$, $q=\Theta(|B|\mathrm{poly}(d))$ and at the
same time $q=\Theta(p^{\alpha})$.777To be precise, we might need to add a
small number of vertices to $P$ or $Q$ without changing the polygons’ shapes
to achieve the desired $p=\Theta(q^{\alpha})$. Since we can solve this
instance in time ${\cal O}((pq)^{1-\varepsilon})={\cal
O}((|A||B|)^{1-\varepsilon}\mathrm{poly}(d))$ by assumption, this would refute
the OV Hypothesis (Hypothesis 2.2). ∎

##  4 3SUM Lower Bound for Scaling and $x$-Translation

Figure 4: Polygon $P$ of the reduction from 3SUM.

In this section we present the reduction from 3SUM to the polygon placement
problem with scaling and $x$-translations. We first describe the reduction and
proceed to proving its correctness. Finally, we also show that polynomial
approximations can be ruled out using the same reduction.

Let $A=\\{a_{1},\dots,a_{n}\\}\subseteq\\{-U,\dots,U\\}$ with $U=n^{3}$ be a
given Average instance. Consider the polygons $P$ and $Q$ depicted in Figures
4 and 5 and let $L$, $L^{\prime}$, $\varepsilon$, and $\delta$ be parameters
that we set later. $P$ is a $(2+2\varepsilon)\times 1$ rectangle $P_{0}$ with
three attached prongs $P_{1},P_{2},P_{3}$, where the prongs have length $L$,
width $2\varepsilon$ and are evenly spread (such that the centers of
neighboring prongs have a distance of $1$). The polygon $Q$ encodes the set
$A$: It is a $(2U+2\delta)\times U$ rectangle $Q_{0}$ with $n$ attached prongs
$Q_{1},\dots,Q_{n}$ whose placement is determined by $A$. Specifically,
consider $2U+1$ evenly spaced segments of width $2\delta$ along the bottom
boundary representing the universe elements $\\{-U,\dots,U\\}$ (see Figure 5
for details). For each $a_{i}\in A$, we attach the prong $A_{i}$ of length
$L^{\prime}$ and width $2\delta$ to the segment representing $a_{i}$. We
choose the values of the parameters as

$\displaystyle L$ $\displaystyle=2U,$ $\displaystyle\varepsilon$
$\displaystyle=\frac{1}{10U},$ $\displaystyle L^{\prime}$ $\displaystyle=UL,$
$\displaystyle\delta$ $\displaystyle=U\varepsilon.$

Finally, for the case that we restrict to scaling and $x$-translation (but not
$y$-translation), we align $P$ and $Q$ along the bottom boundaries of $P_{0}$
and $Q_{0}$, such that any scaling and $x$-translation of $P$ will keep the
bottom boundaries of $P_{0}$ and $Q_{0}$ aligned.

Figure 5: Polygon $Q$ of the reduction from 3SUM.

######  Claim 4.1.

There is a scaling factor $\lambda\geq 1$ such that $\lambda P$ can be
$x$-translated to be contained in $Q$ if and only if there are
$a_{1},a_{2},a_{3}\in A$ such that $a_{2}-a_{1}=a_{3}-a_{2}$.

###### Proof.

Let $a_{1},a_{2},a_{3}\in A$ such that $a_{2}-a_{1}=a_{3}-a_{2}$. We define
$\lambda\coloneqq a_{2}-a_{1}$ and observe that $\lambda\leq U$ by
$a_{1},a_{2},a_{3}\in\\{-U,\dots,U\\}$. We show that $\lambda P$ can be
$x$-translated to be contained in $Q$. Specifically, we align the (vertical
center of the) leftmost prong $P_{1}$ of $\lambda P$ with the (vertical center
of) $Q_{0}$’s bottom boundary segment representing the universe element
$a_{1}$. Since $a_{1}\in A$, $Q$ must have a corresponding prong $Q_{i_{1}}$
for $a_{1}$, and by $\lambda\leq U$, the scaled prong $P_{1}$ has length
$\lambda L\leq UL=L^{\prime}$ and width $\lambda(2\varepsilon)\leq
2U\varepsilon=2\delta$ and hence is contained in $Q_{i_{1}}$. By definition of
$P$ and $Q$, the center of the second prong $P_{2}$ of $\lambda P$ is at
distance $\lambda$ to the center of $P_{1}$ and thus aligned with the center
of the segment of $Q_{0}$ representing
$a_{1}+\lambda=a_{1}+(a_{2}-a_{1})=a_{2}$. Since $a_{2}\in A$, again a
corresponding prong $Q_{i_{2}}$ of sufficient length and width exists, which
contains the scaled $P_{2}$. Finally, in the same way, the third prong $P_{3}$
is aligned with the segment representing $a_{2}+\lambda=2a_{2}-a_{1}=a_{3}$,
and hence is contained in a corresponding prong $Q_{i_{3}}$ of $Q$ since
$a_{3}\in A$.

Conversely, assume that there is a $\lambda\geq 1$ such that $\lambda P$ can
be translated to fit into $Q$ and fix such a translation. Observe that the
bottom boundary of the prongs $P_{1},P_{2},P_{3}$ of $\lambda P$ must be
contained in some prongs $Q_{i_{1}},Q_{i_{2}},Q_{i_{3}}$ of $Q$ — this even
holds if we allow $y$-translation, since we chose $L>U$ and thus $\lambda P$
(which is of height $\lambda(L+1)>U$) cannot be fully contained in $Q_{0}$
(which is of height $U$). For $j\in\\{1,\dots,3\\}$, let $s_{j}$ be the bottom
left vertex of prong $P_{j}$ of $\lambda P$ and let $a_{j}$ be the element of
$A$ represented by prong $Q_{i_{j}}$. Since the distance between $s_{1}$ and
$s_{2}$ is $\lambda$ and these vertices are contained in $2\delta$-width
prongs $Q_{i_{1}},Q_{i_{2}}$ whose centers have distance $a_{2}-a_{1}$, we
conclude that $\lambda\in[(a_{2}-a_{1})-2\delta,(a_{2}-a_{1})+2\delta]$. Thus,
since $s_{3}$ has distance $\lambda$ from $s_{2}$, it must be contained in any
prong whose $x$-dimensions intersect
$[(a_{2}-2\delta)+\lambda,(a_{2}+2\delta)+\lambda]\subseteq[2a_{2}-a_{1}-4\delta,2a_{2}-a_{1}+4\delta]$.
Since $\delta=1/10<1/8$, $Q_{i_{3}}$ is the _unique_ prong intersecting this
range, representing the element $a_{3}=2a_{2}-a_{1}$, which proves that
$a_{2}-a_{1}=a_{3}-a_{2}$, as desired. ∎

We immediately obtain the claimed 3SUM lower bound.

###### Proof of Theorem 1.2.

Observe that the produced polygons are orthogonal and that $P$ and $Q$ have
$12$ and ${\cal O}(n)$ vertices, respectively, and can be constructed in time
${\cal O}(n)$ for any given Average instance. Thus, for any $\varepsilon>0$, a
${\cal O}(n^{2-\varepsilon})$-time algorithm for Polygon Placement would give
a ${\cal O}(n^{2-\varepsilon})$-time algorithm for Average, refuting the 3SUM
Hypothesis by 3SUM-hardness of Average [DGS20]. ∎

In fact, we can even rule out any polynomial approximation factor.

######  Theorem 4.1.

Assuming the 3SUM Hypothesis, there are no $\gamma,\varepsilon>0$ such that,
given orthogonal polygons $P$ and $Q$ of complexity 12 and $q$, we can produce
an estimate $\tilde{\lambda}$ in time ${\cal O}(q^{2-\varepsilon})$ with
$\lambda^{*}\in[\tilde{\lambda},q^{\gamma}\cdot\tilde{\lambda}]$, where
$\lambda^{*}$ is the largest scaling factor $\lambda$ such that $\lambda P$
can be $x$-translated into $Q$.

###### Proof.

Observe that the above proof already reveals that there exists a placement of
$\lambda P$ into $Q$ such that $\lambda P$ intersects more than one prong of
$Q$ if and only if the given Average instance has a solution. Thus, if the
Average instance has a solution, we obtain $\lambda^{*}\geq 1$ by Claim 4.1.
Otherwise, $\lambda P$ cannot intersect more than one prong of $Q$, and thus
must be contained in $Q_{0}\cup Q_{i}$ for some $i$. The only way to do this
is to either use a scaling factor
$\lambda\leq\frac{2\epsilon}{2+\epsilon}<\epsilon$ to fit $\lambda P$ into the
width of a single prong, or use a scaling factor $\lambda\leq U/L$ such that
the prongs’ height can be fully contained in $Q_{0}$. Thus,
$\lambda^{*}\leq\max\\{\epsilon,U/L\\}$. Finally, the claim follows from
observing that in the proof of Claim 4.1 we can choose $\epsilon\leq 1/(10U)$
arbitrarily small and $L\geq 2U$ arbitrarily large. Thus, we can achieve an
arbitrary polynomial gap for $\lambda^{*}$. ∎

##  5 5SUM Lower Bound for Scaling, Translation, and Rotation

In this section we present the reduction from 5SUM to the polygon placement
problem with scaling, translations, and rotation. We first describe the
reduction to then prove its correctness. We reduce from the following version
of 5SUM, which we refer to as 5SUM’: Given sets $A_{1}$, $A_{2}$, $B_{1}$,
$B_{2}$, and $C$, each containing $n$ integers in $\\{-U,\dots,U\\}$ with
$U=n^{5}$, the task is to determine whether there are $a_{1}\in A_{1},a_{2}\in
A_{2},b_{1}\in B_{1},b_{2}\in B_{2}$ and $c\in C$ such that

$b_{2}-b_{1}=a_{2}-a_{1}+c.$

To see that this formulation is indeed 5SUM-hard, reduce any 5SUM instance
$X_{1},\dots,X_{5}\subseteq\\{-U,\dots,U\\}$ to this formulation by defining
$A_{1}=-X_{1},A_{2}=X_{2},B_{1}=X_{3},B_{2}=-X_{4},C=X_{5}$, where
$-X\coloneqq\\{-x\mid x\in X\\}$ for any set $X$. Now observe that $x_{1}\in
X_{1},x_{2}\in X_{2},x_{3}\in X_{3},x_{4}\in X_{4},x_{5}\in X_{5}$ sum up to
zero if and only if
$(a_{1},a_{2},b_{1},b_{2},c)=(-x_{1},x_{2},x_{3},-x_{4},x_{5})\in A_{1}\times
A_{2}\times B_{1}\times B_{2}\times C$ yields a solution to the corresponding
5SUM’ instance.

### Reduction.

Figure 6: Polygon $P$ of reduction for scaling, translation, and rotation.

Figure 7: Polygon $Q$ of reduction for scaling, translation, and rotation.

We now describe the reduction. Let $M$, $L$, $L^{\prime}$, $\varepsilon$, and
$\delta$ be values that we specify later. Given a 5SUM’ instance, we define
the polygons $P$ and $Q$ as illustrated in Figures 7 and 7. Both polygons are
$4n$-gons with ${\cal O}(n)$ attached prongs. Specifically, let $P_{0}$ be the
regular $4n$-gon with side length $4$. We partition the $4n$ sides of $P_{0}$
into $n$ groups, where the $i$-th group consists of two opposing segments
$s^{(i)}_{1},s^{(i)}_{3}$ together with the pair of opposing segments
$s^{(i)}_{2},s^{(i)}_{4}$ that are orthogonal to $s^{(i)}_{1},s^{(i)}_{3}$.
Specifically, $s_{1}^{(1)},s_{2}^{(1)},s_{3}^{(1)},$ and $s_{4}^{(1)}$ denote
the bottom horizontal, right vertical, top horizontal, and left vertical
segments, respectively. The groups $2,\dots,n$ are obtained analogously
through rotation in clockwise direction. At each segment $s^{(i)}_{j}$, we
attach a prong $P^{(i)}_{j}$ — a rectangle of length $L$ and width
$2\varepsilon$ — at a carefully chosen position. In particular, the distance
between the placements of prongs $P_{2}^{(i)}$ and $P_{4}^{(i)}$ will encode
the $i$-th element $c_{i}$ of $C$.

Formally, let us describe the placement of prong $P_{j}^{(i)}$ relative to the
center point of $s_{j}^{(i)}$, according to traversing the segments in anti-
clockwise order (refer to Figure 7 for details). We place the center segments
of $P_{3}^{(i)}$, $P_{4}^{(i)}$, and $P_{1}^{(i)}$ at a distance of $-1$, $0$,
and $0$, respectively, from the center point of the corresponding segment. The
center segment of $P_{2}^{(i)}$ is placed at a distance of
$1+\frac{c_{i}}{M}$, where $c_{i}$ is the $i$-th element in $C$. Crucially, if
we rotate the polygon such that $P_{1}^{(i)}$ is a vertical prong, then the
horizontal centers of $P_{1}^{(i)}$ and $P_{3}^{(i)}$ have a horizontal
distance of $1$, and the vertical centers of prongs $P_{2}^{(i)}$ and
$P_{4}^{(i)}$ have a vertical distance of $1+\frac{c_{i}}{M}$, see Figure 7.

The polygon $Q$ is defined in a similar way, see Figure 7: It is defined as a
regular $4n$-gon $Q_{0}$ of side length $10M$ where we attach to each side
either a _set gadget_ (consisting of $n$ prongs of width $2\delta$ and length
$L^{\prime}$) or a _trivial gadget_ , i.e., a large, rotated $8M\times
L^{\prime}$ rectangle which can fit any reasonably placed prong of $P$. The
idea is that any large copy of $P$ must be rotated such that the prongs
$P_{1}^{(i)},P_{2}^{(i)},P_{3}^{(i)},P_{4}^{(i)}$ must fit into the set
gadgets $S(A_{1}),S(B_{1}),S(A_{2}),S(B_{2})$ as defined in Section 4, Figure
5. Specifically, at the horizontal and vertical segments of $Q_{0}$ we place
the set gadgets $S(A_{1}),S(B_{1}),S(A_{2}),S(B_{2})$ relative to the center
points in the following way (according to an anticlockwise traversal of the
segments): we place $S(B_{1})$, $S(A_{1}),S(B_{2}),S(A_{2})$ such that they
are centered around the distance $0,0,M,-M$ from the start point of the
corresponding segment. In this way, the horizontal centers of $S(A_{1})$,
$S(A_{2})$ have a horizontal distance of $M$ and the vertical centers of
$S(B_{1})$, $S(B_{2})$ have a vertical distance of $M$. For all remaining
segments, we place trivial gadgets centered around the center point of the
corresponding gadget.

We choose the parameters as follows:888These parameters are not optimized to
have the smallest possible bit length. In any case, all coordinates in the
description of the produced instance will remain polynomially bounded.

$\displaystyle M$ $\displaystyle=U^{2}n,$ $\displaystyle L$
$\displaystyle=50n,$ $\displaystyle\varepsilon$
$\displaystyle=\frac{1}{800Mn},$ $\displaystyle L^{\prime}$
$\displaystyle=2ML,$ $\displaystyle\delta$ $\displaystyle=\frac{1}{400}.$

### Correctness.

We show that this construction gives a Polygon Placement instance equivalent
to the given 5SUM’ instance. We split the proof into two lemmas, one for each
direction. For the next two proofs, recall that for any
$x,y,\varepsilon\in\mathbb{R}$, we use $x\in y+[-\varepsilon,\varepsilon]$ to
mean $x\in[y-\varepsilon,y+\varepsilon]$.

######  Lemma 5.1.

If there are $a_{1}\in A_{1},a_{2}\in A_{2},b_{1}\in B_{1},b_{2}\in B_{2}$ and
$c\in C$ such that $b_{2}-b_{1}=a_{2}-a_{1}+c$, then there is a scaling factor
$\lambda\geq M-2U$ such that $\lambda P$ can be rotated and translated to be
contained in $Q$.

###### Proof.

Let $a_{1}\in A_{1},a_{2}\in A_{2},b_{1}\in B_{1},b_{2}\in B_{2}$ and
$i^{*}\in\\{1,\dots,n\\}$ be such that $b_{2}-b_{1}=a_{2}-a_{1}+c_{i^{*}}$
where $c_{i^{*}}$ is the $i^{*}$-th element of $C$. We claim that we can place
$\lambda P$ with scaling factor $\lambda=M+a_{2}-a_{1}$ by translating its
origin by $\tau=(a_{1},b_{1})$ and rotating the polygon by an angle of
$-2\pi\frac{i^{*}-1}{4n}$ around its origin. Note that this implies
$\lambda\in[M-2U,M+2U]$.

We first observe that under this scaling, rotation and translation, $P_{0}$
fits into $Q_{0}$: We can conservatively approximate $P_{0}$ and $Q_{0}$ by
their circumscribed circle and inscribed circle, respectively, whose radii are
the circumradius $R_{P_{0}}$ and the apothem $a_{Q_{0}}$, respectively. Since
their side lengths are $4\lambda$ and $10M$, respectively, we notice by Fact
2.1 and $\left\lVert\tau\right\rVert_{2}\leq\sqrt{2}U$ that

$R_{P_{0}}+\left\lVert\tau\right\rVert_{2}\leq 4\lambda n+\sqrt{2}U\leq
4(M+2U)n+\sqrt{2}U\leq 5Mn\leq a_{Q_{0}},$

where the second-to-last inequality follows from $M=U^{2}n\geq 8Un+\sqrt{2}U$
for sufficiently large $n$, as $U=n^{5}$. Thus, when shifting an arbitrarily
rotated $\lambda P$ by $\tau$, $P_{0}$ will remain in the inscribed circle of
$Q_{0}$.

It remains to show that each prong $P_{j}^{(i)}$ fits into $Q$ under this
placement. We first consider the most important case of $i=i^{*}$. Note that
by the chosen rotation, we have that
$P_{1}^{(i^{*})},P_{2}^{(i^{*})},P_{3}^{(i^{*})}$ and $P_{4}^{(i^{*})}$ are
the bottom horizontal, right vertical, top horizontal and left vertical prongs
of $\lambda P$. We claim that the part of $P_{1}^{(i^{*})}$ that leaves
$Q_{0}$ is contained in the prong in $S(A_{1})$ representing $a_{1}$. Indeed,
note that the center segment of $P_{1}^{(i^{*})}$ intersects the bottom
segment of $Q_{0}$ at an $\mathrm{x}$-coordinate of $\tau_{\mathrm{x}}=a_{1}$.
As $\lambda\leq M+2U\leq 2M$, we have that $P_{1}^{(i^{*})}$ is a prong of
width $2\lambda\varepsilon\leq 4M\varepsilon\leq\frac{1}{200n}\leq 2\delta$
and length $\lambda L\leq 2ML=L^{\prime}$. Hence, this part fits fully into
the width-$2\delta$, length-$L^{\prime}$ prong of $S(A_{1})$ centered at
$\mathrm{x}$-coordinate $a_{1}$. Likewise, the center segment of prong
$P_{4}^{(i^{*})}$ intersects the left vertical segment at a
$\mathrm{y}$-coordinate of $\tau_{\mathrm{y}}=b_{1}$, and thus the prong
$P_{4}^{(i^{*})}$ is fully contained in the union of $Q_{0}$ and the prong
representing $b_{1}$ in $S(B_{1})$ (attached at $\mathrm{y}$-coordinates
$b_{1}+[-\delta,\delta]$). For prong $P_{3}^{(i^{*})}$, we observe that its
center segment intersects the top horizontal segment of $Q_{0}$ at
$\mathrm{x}$-coordinate
$\tau_{\mathrm{x}}+\lambda=a_{1}+(M+a_{2}-a_{1})=M+a_{2}$. Thus,
$P_{3}^{(i^{*})}$ is fully contained in the union of $Q_{0}$ and the prong
representing $a_{2}$ in $S(A_{2})$ (attached at $\mathrm{x}$-coordinates
$M+a_{2}+[-\delta,\delta]$). Finally, the center segment of prong
$P_{2}^{(i^{*})}$ intersects the right vertical segment of $Q_{0}$ at a
$\mathrm{y}$-coordinate of

$\tau_{y}+\lambda\left(1+\frac{c_{i^{*}}}{M}\right)=b_{1}+(M+a_{2}-a_{1})\left(1+\frac{c_{i^{*}}}{M}\right)=b_{1}+M+a_{2}-a_{1}+c_{i^{*}}+\frac{(a_{2}-a_{1})c_{i^{*}}}{M}.$

Using that $b_{1}+a_{2}-a_{1}+c_{i^{*}}=b_{2}$ by assumption, and that
$\left|\frac{(a_{2}-a_{1})c_{i^{*}}}{M}\right|\leq\frac{2U^{2}}{M}=\frac{2}{n}$,
we obtain that the prong $P_{2}^{(i^{*})}$ intersects the right vertical
segment of $Q_{0}$ at a $\mathrm{y}$-coordinate of
$M+b_{2}+[-(\lambda\varepsilon+\frac{2}{n}),\lambda\varepsilon+\frac{2}{n}]$.
By noting that $\lambda\varepsilon+\frac{2}{n}\leq
2M\varepsilon+\frac{2}{n}=\frac{1}{400n}+\frac{2}{n}\leq\frac{1}{400}=\delta$
for sufficiently large $n$, this range is fully contained in the range
$M+b_{2}+[-\delta,\delta]$ given by the prong representing $b_{2}$ in
$S(B_{2})$, which thus contains the relevant part of $P_{2}^{(i^{*})}$. We
conclude that each prong of the $i^{*}$-th group fits into $Q_{0}$.

It remains to argue that each prong $P_{j}^{(i)}$ with $i\neq i^{*}$ fits into
$Q_{0}$. This claim is essentially trivial: Imagine a rotation of coordinate
axes such that $P_{j}^{(i)}$ is a vertical prong. It is easy to see that
$P_{j}^{(i)}$ intersects the bottom segment of $Q_{0}$ at
$\mathrm{x}$-coordinates in $[-2M,2M]$. The corresponding $4M\times
L^{\prime}$ rectangle below $Q_{0}$ is contained in the trivial gadget, and
thus can contain the part of $P_{j}^{(i)}$ leaving $Q_{0}$. This concludes the
lemma. ∎

We now show the converse of Lemma 5.1.

######  Lemma 5.2.

If there is a scaling factor $\lambda\geq M-2U$ such that $\lambda P$ can be
rotated and translated to be contained in $Q$, then there are $a_{1}\in
A_{1},a_{2}\in A_{2},b_{1}\in B_{1},b_{2}\in B_{2}$ and $c\in C$ such that
$b_{2}-b_{1}=a_{2}-a_{1}+c$.

###### Proof.

Assume that there is a scaling factor $\lambda\geq M-2U$ such that $\lambda P$
can be placed into $Q$ (under rotation and translation) and fix such a
placement of $\lambda P$. Specifically, let $\lambda\geq M-2U$ be the scaling
factor, $\tau\in\mathbb{R}^{2}$ denote the translation of the center of
$\lambda P$, and let $\alpha\in[0,2\pi)$ denote the rotation angle of $\lambda
P$ around its center (in counter clockwise direction). In the remainder of
this proof, we show that the following sequence of statements holds:

  1. (1)

The rotation angle $\alpha$ is in
$-2\pi\cdot\frac{i}{4n}+[-\varepsilon_{\mathrm{rot}},\varepsilon_{\mathrm{rot}}]$
for some $i\in\\{0,\dots,4n-1\\}$ and
$\varepsilon_{\mathrm{rot}}\coloneqq\frac{\delta}{Mn}$. Furthermore, there is
some prong $P^{(i^{*})}_{j^{*}}$ that intersects the set gadget $S(A_{1})$.

  2. (2)

We have $j^{*}\in\\{1,3\\}$ and there are $a_{1}\in A_{1},a_{2}\in A_{2}$ such
that the $x$-translation $\tau_{\mathrm{x}}$ is within
$a_{1}+[-\varepsilon_{\mathrm{trans}},\varepsilon_{\mathrm{trans}}]$ (if
$j^{*}=1$) or within
$M+a_{2}+[-\varepsilon_{\mathrm{trans}},\varepsilon_{\mathrm{trans}}]$ (if
$j^{*}=3$) and the scaling factor $\lambda$ is within
$M+a_{2}-a_{1}+[-\varepsilon_{\mathrm{scale}},\varepsilon_{\mathrm{scale}}]$,
where $\varepsilon_{\mathrm{trans}}\coloneqq 21\delta$ and
$\varepsilon_{\mathrm{scale}}\coloneqq 43\delta$.

  3. (3)

If $j^{*}=1$, then there is some $b_{1}\in B_{1}$ such that the
$y$-translation $\tau_{\mathrm{y}}$ is within
$b_{1}+[-\varepsilon_{\mathrm{trans}},\varepsilon_{\mathrm{trans}}]$. If
$j^{*}=3$, there is some $b_{2}\in B_{2}$ such that the $y$-translation
$\tau_{\mathrm{y}}$ is within
$M+b_{2}+[-\varepsilon_{\mathrm{trans}},\varepsilon_{\mathrm{trans}}]$.

  4. (4)

Finally, there is a corresponding $b_{2}\in B_{2}$ (if $j^{*}=1$) or $b_{1}\in
B_{1}$ (if $j^{*}=3$) such that $b_{2}-b_{1}=a_{2}-a_{1}+c_{i*}$.

After showing the above statements, we can then deduce that any placement of
$\lambda P$ in $Q$ where $\lambda\geq M-U$ uniquely defines $a_{1}\in
A_{1},a_{2}\in A_{2},b_{1}\in B_{1},b_{2}\in B_{2},c\in C$ such that
$b_{2}-b_{1}=a_{2}-a_{1}+c$.

We first collect general useful facts: By $M=U^{2}n$, we have
$M-2U=M(1-2/(Un))\geq 0.9M$ for sufficiently large $n$, which we will use as a
lower bound for $\lambda$. A trivial upper bound is given by $\lambda\leq 3M$,
as otherwise already the scaled $P_{0}$ (of side length more than $12M$)
cannot fit into $Q$ (of side length $10M$). By Fact 2.1, the regular $4n$-gon
$Q_{0}$ with side length $10M$ has a circumradius $R\leq 10Mn$. Thus, the
diameter of $Q_{0}$ is bounded by $2R\leq 20Mn$, which we will frequently
exploit.

To prove (1), note that since $\lambda L\geq 0.9ML=45Mn>20Mn\geq 2R$, each
prong of $\lambda P$ (each of length $\lambda L$) cannot be fully contained in
$Q_{0}$, but must intersect either a set gadget or a trivial gadget. In fact,
by the structure of $P$ and $Q$, every prong $P_{j}^{(i)}$ of $\lambda P$ must
intersect a _unique_ (set or trivial) gadget of $Q$. In particular, let
$P_{j^{*}}^{(i^{*})}$ denote the prong of $\lambda P$ intersecting $S(A_{1})$.
We will show that the rotation angle is very close to
$-2\pi\cdot\frac{(j^{*}-1)n+i^{*}-1}{4n}$: Let
$\beta\coloneqq\alpha+2\pi\cdot\frac{(j^{*}-1)n+i^{*}-1}{4n}$ be the
difference of $\alpha$ and this angle. Observe that the center segment of
$P_{j^{*}}^{(i^{*})}$ has an intersection of length at least $\lambda L-2R\geq
45Mn-20Mn=25Mn$ inside a prong of $S(A_{1})$ and cannot traverse a horizontal
distance of more than $2\delta$ (as any prong of $S(A_{1})$ has width
$2\delta$). Since under rotation angle $\alpha$, $P_{j^{*}}^{(i^{*})}$
traverses a horizontal distance of at least $25Mn\cdot|\sin(\beta)|$, we must
have that $|\sin(\beta)|\leq\frac{2\delta}{25Mn}$, and thus by Fact 2.1,
$|\beta|\leq(\pi/2)\cdot|\sin(\beta)|\leq
2\cdot\frac{2\delta}{25Mn}\leq\frac{\delta}{Mn}$, concluding the proof of (1).

To prove (2), let $P_{\mathrm{top}}$ denote the prong opposite of
$P_{j^{*}}^{(i^{*})}$. Note that if $j^{*}\in\\{2,4\\}$ then
$P_{\mathrm{top}}$ is to the left of $S(A_{1})$, and hence cannot intersect
$S(A_{2})$ (the unique gadget that $P_{\mathrm{top}}$ must intersect), as
$P_{\mathrm{top}}$ is located to the right of $S(A_{1})$. Thus, we must have
$j^{*}\in\\{1,3\\}$. If $j^{*}=1$, then for $P_{j^{*}}^{(i^{*})}$ to intersect
some prong of $S(A_{1})$, the translation $\tau_{x}$ must be such that the
center segment of $P_{j^{*}}^{(i^{*})}$ intersects the bottom horizontal
segment of $Q_{0}$ at some prong of $S(A_{1})$, i.e., at an
$\mathrm{x}$-coordinate in $a_{1}+[-\delta,\delta]$ for some $a_{1}\in A_{1}$.
Note that the center line of $P_{j^{*}}^{(i^{*})}$ runs through the origin of
$P$ and that any segment of $Q_{0}$ is at distance at most $2R$ from the
translated center of $\lambda P$. Thus, by the Line Rotation Lemma 2.2
(setting $\Delta=0,Y=2R,\varepsilon=\varepsilon_{\mathrm{rot}}$), the center
segment intersects $Q_{0}$’s bottom segment at an $\mathrm{x}$-coordinate in
$\tau_{\mathrm{x}}+[-2R\varepsilon_{\mathrm{rot}},2R\varepsilon_{\mathrm{rot}}]$.
For $a_{1}+[-\delta,\delta]$ and
$\tau_{x}+[-2R\varepsilon_{\mathrm{rot}},2R\varepsilon_{\mathrm{rot}}]$ to
intersect, $\tau_{\mathrm{x}}$ must be in
$a_{1}+[-(\delta+2R\varepsilon_{\mathrm{rot}}),\delta+2R\varepsilon_{\mathrm{rot}}]$.
By observing that
$2R\varepsilon_{\mathrm{rot}}\leq\frac{20Mn\delta}{Mn}=20\delta$, we obtain
that $\tau_{\mathrm{x}}$ is indeed in $a_{1}+[-21\delta,21\delta]$. For the
scaling factor, recall that the center segment of the opposite prong
$P_{\mathrm{top}}$ must intersect some prong of $S(A_{2})$, i.e., at some
$\mathrm{x}$-coordinate in $M+a_{2}+[-\delta,\delta]$ for some $a_{2}\in
A_{2}$. By the Line Rotation Lemma 2.2 (setting
$\Delta=\lambda,Y=2R,\varepsilon=\varepsilon_{\mathrm{rot}}$), the center
segment intersects the top horizontal segment of $Q_{0}$ at an
$\mathrm{x}$-coordinate in
$\tau_{\mathrm{x}}+[\lambda-2R\varepsilon_{\mathrm{rot}},\lambda(1+\varepsilon_{\mathrm{rot}}^{2})+2R\varepsilon_{\mathrm{rot}}]$.
Since $\tau_{\mathrm{x}}$ is in $a_{1}+[-21\delta,21\delta]$ and
$\lambda\varepsilon_{\mathrm{rot}}^{2}\leq
3M\varepsilon_{\mathrm{rot}}^{2}=\frac{3\delta^{2}}{Mn^{2}}\leq\delta$, we
obtain that the intersection has an $\mathrm{x}$-coordinate in
$a_{1}+\lambda+[-(2R\varepsilon_{\mathrm{rot}}+21\delta),2R\varepsilon_{\mathrm{rot}}+22\delta]$.
Since $2R\varepsilon_{\mathrm{rot}}\leq 20\delta$, and
$a_{1}+\lambda+[-42\delta,42\delta]$ intersects $M+a_{2}+[-\delta,\delta]$, we
obtain that $\lambda$ is in $M+a_{2}-a_{1}+[-43\delta,43\delta]$.

If $j^{*}=3$, i.e., $P$ is as before, but rotated by $\pi$, the calculations
are analogous, but choose first $a_{2}$, then $a_{1}$: For $P_{\mathrm{top}}$
to intersect $S(A_{2})$, the $x$-translation $\tau_{\mathrm{x}}$ must be in
$M+a_{2}+[-21\delta,21\delta]$ for some $a_{2}\in A_{2}$. Correspondingly, for
$P_{j^{*}}^{(i^{*})}$ to intersect $S(A_{1})$, the scaling factor $\lambda$
must be in $M+a_{2}-a_{1}+[-43\delta,43\delta]$ for some $a_{1}\in A_{1}$.

To prove (3), let $P_{\mathrm{left}}$ ($P_{\mathrm{right}}$) denote the prongs
in the $i^{*}$-th group following (preceding) $P_{j^{*}}^{(i^{*})}$ in
clockwise order, i.e., $P_{\mathrm{left}},P_{\mathrm{right}}$ must intersect
$S(B_{1}),S(B_{2})$, respectively. If $j^{*}=1$, then the intersection of the
center line of $P_{j^{*}}^{(i^{*})}$ with the left vertical segment of $Q_{0}$
is, by the Line Rotation Lemma 2.2 (with
$\Delta=0,Y=2R,\varepsilon=\varepsilon_{\mathrm{rot}}$, appropriately
rotated), at a $\mathrm{y}$-coordinate of
$\tau_{\mathrm{y}}+[-2R\varepsilon_{\mathrm{rot}},2R\varepsilon_{\mathrm{rot}}]$.
For this to intersect $b_{1}+[-\delta,\delta]$ for some $b_{1}\in B_{1}$, we
must have that $\tau_{y}$ is within
$b_{1}+[-(\delta+2R\varepsilon_{\mathrm{rot}}),\delta+2R\varepsilon_{\mathrm{rot}}]$.
Since, $2R\varepsilon_{\mathrm{rot}}\leq 20\delta$, we conclude that
$\tau_{\mathrm{y}}$ is within $b_{2}+[-21\delta,21\delta]$. If $j^{*}=3$, then
the center line of $P_{\mathrm{right}}$ intersects the right vertical segment
of $Q_{0}$ at
$\tau_{y}+[-2R\varepsilon_{\mathrm{rot}},2R\varepsilon_{\mathrm{rot}}]$ by the
Line Rotation Lemma 2.2. For this to intersect some prong of $S(B_{2})$, it
must intersect $M+b_{2}+[-\delta,\delta]$ for some $b_{2}\in B_{2}$.
Analogously to before, we conclude that $\tau_{\mathrm{y}}$ is within
$M+b_{2}+[-21\delta,21\delta]$.

Finally, we can prove (4): If $j^{*}=1$, then recall that
$\tau_{\mathrm{x}},\tau_{\mathrm{y}}$ and $\lambda$ are in
$a_{1}+[-\varepsilon_{\mathrm{trans}},\varepsilon_{\mathrm{trans}}],b_{1}+[-\varepsilon_{\mathrm{trans}},\varepsilon_{\mathrm{trans}}]$
and
$M+a_{2}-a_{1}+[-\varepsilon_{\mathrm{scale}},\varepsilon_{\mathrm{scale}}]$
and that the prong $P_{\mathrm{right}}$ must intersect some prong in
$S(B_{2})$. The intersection of the center segment of $P_{\mathrm{right}}$
with the right vertical segment of $Q_{0}$ is, by the Line Rotation Lemma 2.2
(with $\Delta=\lambda(1+\frac{c_{i^{*}}}{M}),Y=2R$, appropriately rotated) at
a $\mathrm{y}$-coordinate within
$\tau_{y}+[\lambda(1+\frac{c_{i^{*}}}{M})-2R\varepsilon_{\mathrm{rot}},\lambda(1+\frac{c_{i^{*}}}{M})(1+\varepsilon_{\mathrm{rot}}^{2})+2R\varepsilon_{\mathrm{rot}}]$.
Noting that $2R\varepsilon_{\mathrm{rot}}\leq 20\delta$ and
$\lambda(1+\frac{c_{i^{*}}}{M})\varepsilon_{\mathrm{rot}}^{2}\leq
3M(1+\frac{U}{M})\varepsilon_{\mathrm{rot}}^{2}\leq
6M\varepsilon_{\mathrm{rot}}^{2}=\frac{6\delta^{2}}{Mn^{2}}\leq\delta$ for
sufficiently large $n$, we conclude that the intersection is at some
$\mathrm{y}$-coordinate in
$\tau_{\mathrm{y}}+\lambda(1+\frac{c_{i^{*}}}{M})+[-21\delta,21\delta]$.
Observe that by $\lambda$ being in $M+a_{2}-a_{1}+[-43\delta,43\delta]$ and
$1+\frac{c_{i^{*}}}{M}\leq 2$, we have that
$\lambda\left(1+\frac{c_{i^{*}}}{M}\right)$ is within

$M+a_{2}-a_{1}+c_{i^{*}}+\frac{c_{i^{*}}(a_{2}-a_{1})}{M}+[-86\delta,86\delta]$

and hence within

$M+a_{2}-a_{1}+c_{i^{*}}+[-(86\delta+\frac{2U^{2}}{M}),86\delta+\frac{2U^{2}}{M}].$

By choice of $M$, we have $\frac{2U^{2}}{M}=\frac{2}{n}\leq\delta$ for
sufficiently large $n$. Thus, the intersection of the center line of prong
$P_{\mathrm{right}}$ with the right vertical segment of $Q_{0}$ is at
$\tau_{\mathrm{y}}+M+a_{2}-a_{1}+c_{i^{*}}+[-(87\delta+21\delta),87\delta+21\delta]$.
Using that $\tau_{\mathrm{y}}$ is within $b_{1}+[-21\delta,21\delta]$, we
conclude that the intersection is at
$M+b_{1}+a_{2}-a_{1}+c_{i*}+[-129\delta,129\delta]$. For this intersection to
be contained in $M+b_{2}+[-\delta,\delta]$ for some $b_{2}\in B_{2}$, we must
have that

$|(M+b_{2})-(M+b_{1}+a_{2}-a_{1}+c_{i^{*}})|\leq 130\delta.$

Since $130\delta<1/2$ and
$|(M+b_{2})-(M+b_{1}+a_{2}-a_{1}+c_{i^{*}})|=|b_{2}-(b_{1}+a_{2}-a_{1}+c_{i^{*}})|$
is integral, we conclude that the unique possibility is that there exists
$b_{2}\in B_{2}$ which satisfies $b_{2}=b_{1}+a_{2}-a_{1}+c_{i^{*}}$.

Analogous calculations show the statement for the case of $j^{*}=3$: We
already know that $\tau_{\mathrm{x}},\tau_{\mathrm{y}}$ and $\lambda$ are in
$M+a_{1}+[-\varepsilon_{\mathrm{trans}},\varepsilon_{\mathrm{trans}}],M+b_{2}+[-\varepsilon_{\mathrm{trans}},\varepsilon_{\mathrm{trans}}]$
and
$M+a_{2}-a_{1}+[-\varepsilon_{\mathrm{scale}},\varepsilon_{\mathrm{scale}}]$.
Analogously to above, the intersection of the center segment of
$P_{\mathrm{left}}$ with the left vertical segment of $Q_{0}$ can be shown to
be within $b_{2}-(a_{2}-a_{1}+c_{i^{*}})+[-129\delta,129\delta]$. For this to
intersect some prong in $S(B_{1})$, i.e., $b_{1}+[-\delta,\delta]$ for some
$b_{1}\in B_{1}$, we must have $|b_{1}-(b_{2}-a_{2}+a_{1}-c_{i^{*}}|\leq
82\delta$, which by $130\delta<\frac{1}{2}$ and integrality of the left hand
side proves $b_{1}=b_{2}-a_{2}+a_{1}-c_{i^{*}}$ is in $B_{1}$. ∎

Finally, we can prove the result of this section.

###### Proof of Theorem 1.5.

The equivalence between the polygon containment and the 5SUM’ instance is
shown in Lemmas 5.1 and 5.2. It only remains to argue that the claimed lower
bound follows. Observe that $P$ is a $4n$-gon with attached rectangles at all
sides and thus consists of ${\cal O}(n)$ vertices. The polygon $Q$ also is a
$4n$-gon with constant complexity rectangles attached at all sides, however,
it additionally has gadgets on the bottom, right, top, and left. Each of these
four gadgets has complexity ${\cal O}(n)$ and thus $Q$ has complexity ${\cal
O}(n)$. Thus, since it is straightforward to compute the $O(n)$-vertex
polygons $P$ and $Q$ in linear time, the lower bound follows. ∎

##  6 4SUM Lower Bound for Scaling and Arbitrary Translation

After having established the 5SUM-hardness for scaling, translation, and
rotation (Theorem 1.5), it is immediate how to obtain Theorem 1.3.

###### Proof of Theorem 1.3.

The proof follows from simplifying the reduction in the proof of Theorem 1.5
in the previous section by viewing $C$ as a singleton set containing $0$, and
using a single group instead of $n$ groups. It is straightforward to adapt the
proof of correctness and to observe that $P$ simplifies to a square with $4$
attached prongs, resulting in a constant-sized polygon. ∎

##  7 Algorithm for Scaling and Translation

We will prove Theorem 1.4 by a reduction to the following offline dynamic
problem that we refer to as Offline Dynamic Rectangle Cover: Let $\mathcal{S}$
be a set of $n$ rectangles in $[1,N]\times[1,N]$ with $N={\cal O}(n)$. The
input is a sequence of $U$ updates $u_{1},\dots,u_{U}$, where an update comes
in two flavors:

  * •

delete a rectangle in $\mathcal{S}$, or

  * •

add a rectangle with integral coordinates in $[1,N]\times[1,N]$ to
$\mathcal{S}$,

such that each update maintains $|\mathcal{S}|\leq n$. The task is to
determine the first update $u_{i}$ after which $\mathcal{S}$ does not cover
$[1,N]\times[1,N]$. Our main algorithmic contribution is to prove the
following reduction. Recall that, given two polygons $P$ and $Q$,
$\lambda^{*}$ is defined as the largest scaling factor $\lambda$ such that
$\lambda P$ can be placed into $Q$ under translations.

######  Lemma 7.1.

Let $T(n,U)$ denote the optimal running time for solving Offline Dynamic
Rectangle Cover. Then, given any orthogonal simple polygons $P$ and $Q$ with
$p$ and $q$ vertices, respectively, we can compute $\lambda^{*}$ in time
${\cal O}((pq)^{2}\log(pq)+T(pq,(pq)^{2}))$.

Thus, we first show how Lemma 7.1 implies Theorem 1.4, to then dedicate the
remainder of this section to proving Lemma 7.1. To this end, we can plug in an
offline dynamic algorithm due to Overmars and Yap [OY91], and as improved by
[Cha10].

###### Proof of Theorem 1.4.

Building on Overmars and Yap [OY91], Chan [Cha10] shows how to maintain the
area (in a prespecified box) of the union of at most $n$ rectangles under
${\cal O}(n)$ pregiven999Actually, these algorithms only require advance
knowledge of the vertices of the rectangles. insertions or deletions of
rectangles (never exceeding $n$ rectangles), in amortized time ${\cal
O}(\sqrt{n}2^{{\cal O}(\log^{*}n)})$ per update.

Thus, to answer $U\geq n$ updates in Offline Dynamic Rectangle Cover, we can
divide all updates into ${\cal O}(U/n)$ batches of at most $n$ updates. For
each batch, we use Chan’s data structure as follows: we use at most $n$
insertions to create the initial state at the start of the batch. We then
perform each update in the batch, stopping if the area becomes strictly less
than $(N-1)^{2}$ and returning this update. Observe that the at most $2n$
updates to Chan’s data structure for the current batch are determined in
advance. Thus, the total time to perform these updates is ${\cal
O}(n\sqrt{n}2^{{\cal O}(\log^{*}n)})$. Doing this for all ${\cal O}(U/n)$
batches results in a total time of $T(n,U)={\cal
O}(\frac{U}{n}n\sqrt{n}2^{{\cal O}(\log^{*}n)})={\cal O}(U\sqrt{n}2^{{\cal
O}(\log^{*}n)})$.

Plugging in $n={\cal O}(pq)$ and $U={\cal O}((pq)^{2})$, we obtain a running
time of ${\cal O}((pq)^{2.5}2^{{\cal O}(\log^{*}pq)})$ for determining
$\lambda^{*}$ for the orthogonal polygons $P,Q$ with $p$ and $q$ vertices,
respectively. Given $\lambda^{*}$, we can also find a feasible translation for
$\lambda^{*}P$ using the algorithm for the fixed-size case [Her96] in time
${\cal O}(pq\log(pq))$, which does not affect the overall running time. ∎

In the remainder of this section, we prove Lemma 7.1. Let $P$ and $Q$ be
centered at the origin (i.e., their bounding boxes have the origin as their
center) and let $B=[x^{B}_{0},x^{B}_{1}]\times[y^{B}_{0},y^{B}_{1}]$ denote
the bounding box of $Q$. Cover $P$ by rectangles $P_{1}\dots,P_{p^{\prime}}$
with $p^{\prime}={\cal O}(p)$ and $\mathbb{R}^{2}\setminus Q$ by rectangles
$Q_{1},\dots,Q_{q^{\prime}}$ with $q^{\prime}={\cal O}(q)$, where
$\mathbb{R}^{2}\setminus Q$ denotes the set of points in the plane that do not
lie inside $Q$. (To see that this is possible, repeatedly chop off concavities
of $P$. Similarly for $Q$, use four rectangles to cover
$\mathbb{R}^{2}\setminus B$ and repeatedly chop off concavities of each
connected part in $B\setminus Q$.) For $i\in[p^{\prime}],j\in[q^{\prime}]$,
let $R_{i,j}(\lambda)$ denote the set of translations of $\lambda P$ such that
$P_{i}$ (under this scaling and translation) intersects $Q_{j}$ in its
interior, more formally

$R_{i,j}(\lambda)\coloneqq\\{\tau\in\mathbb{R}^{2}|(\lambda
P_{i}+\tau)\cap(Q_{j}\setminus\partial Q_{j})\neq\emptyset\\},$

where $\partial Q_{j}$ is the boundary of $Q_{j}$ and $\lambda P_{i}$ is
scaled with the center of $P$ as reference point.

######  Proposition 7.1 ([AB89],[Her96, Proposition 1]).

For any $\lambda$, $\lambda P$ can be translated to be contained in $Q$ if and
only if $\bigcup_{i,j}R_{i,j}(\lambda)$ does not cover $B$.

###### Proof.

Note that if $\tau\in\mathbb{R}^{2}$ is a translation such that $\lambda P$
fits into $Q$, $\tau$ must be a translation in $B$ (as the center of $P$ must
be contained in $Q$) and no $P_{i}$ may intersect some $Q_{j}$ in its
interior. Thus, any such $\tau$ must be in
$B\setminus\bigcup_{i,j}R_{i,j}(\lambda)$. Conversely, if we translate
$\lambda P$ by some $\tau\in B\setminus\bigcup_{i,j}R_{i,j}(\lambda)$, it must
be fully contained in $Q$, as it has no intersection with
$\mathbb{R}^{2}\setminus Q$. ∎

Note that each $R_{i,j}$ is of the form

$R_{i,j}(\lambda)=(a_{i,j}(\lambda),b_{i,j}(\lambda))\times(c_{i,j}(\lambda),d_{i,j}(\lambda)),$

where each $a_{i,j},b_{i,j},c_{i,j},d_{i,j}$ is a linear function in
$\lambda$. Crucially, while the coordinates of virtually all
$R_{i,j}(\lambda)$’s change with each change in $\lambda$, we will work in
_rank space_ and only consider changes in the _combinatorial structure_ of the
arrangement of the $R_{i,j}(\lambda)$’s. To this end, define

$\displaystyle\mathcal{X}$
$\displaystyle\coloneqq\\{a_{i,j}(\lambda)\mid(i,j)\in[p^{\prime}]\times[q^{\prime}]\\}\cup\\{b_{i,j}(\lambda)\mid(i,j)\in[p^{\prime}]\times[q^{\prime}]\\}\cup\\{x_{0}^{B},x_{1}^{B}\\}$
$\displaystyle\mathcal{Y}$
$\displaystyle\coloneqq\\{c_{i,j}(\lambda)\mid(i,j)\in[p^{\prime}]\times[q^{\prime}]\\}\cup\\{d_{i,j}(\lambda)\mid(i,j)\in[p^{\prime}]\times[q^{\prime}]\\}\cup\\{y_{0}^{B},y_{1}^{B}\\}$

as the sets of relevant $\mathrm{x}$\- and $\mathrm{y}$-coordinates,
respectively. We will exploit that the sorted orders of $\mathcal{X}$ and
$\mathcal{Y}$ change only at ${\cal O}((pq)^{2})$ many values of $\lambda$,
which is the case as each pair of elements can swap at most once due to
linearity in $\lambda$. To argue about these orderings, for any $\lambda$, we
write $x_{1}(\lambda)\leq x_{2}(\lambda)\leq\dots\leq
x_{|\mathcal{X}|}(\lambda)$ for the sorted order of $\mathcal{X}$ under
$\lambda$. Let $\mathrm{rank}_{\lambda}(x)$ of an $x\in\mathcal{X}$ denote the
rank of $x$ in the sorted order of $\mathcal{X}$ – note that since different
elements in $\mathcal{X}$ might have the same value under $\lambda$, this
value is not uniquely determined. Thus, we define $\mathrm{rank}_{\lambda}(x)$
as the interval $I$ of indices $i$ such that $x_{i}(\lambda)=x(\lambda)$. Note
that $\mathrm{rank}_{\lambda}(x)$ is always an interval in
$\\{1,\dots,|\mathcal{X}|\\}$. We use the analogous notion of
$\mathrm{rank}_{\lambda}(y)$ for any $y\in\mathcal{Y}$ to denote the interval
of elements equal to $y(\lambda)$ in the sorted order of $\mathcal{Y}$ under
$\lambda$.

A technical complication is that all $R_{i,j}(\lambda)$’s are _open_
rectangles, while we aim to reduce to the problem of maintaining a union of
closed rectangles. We overcome this complication by replacing each rank value
$r\in\\{1,\dots,|\mathcal{X}|\\}$ by two (symbolic) coordinates
$\mathrm{end}(r),\mathrm{start}(r)$, with the understanding that
$\mathrm{end}(r)$ is used for open intervals ending at $r$ and
$\mathrm{start}(r)$ is used for open intervals starting in $x$. For intuition,
one may think of $\mathrm{end}(r)$ and $\mathrm{start}(r)$ as $r-\varepsilon$
and $r+\varepsilon$, respectively. The corresponding set

$\mathcal{A}\coloneqq\bigcup_{r\in[|\mathcal{X}|]}\\{\mathrm{end}(r),\mathrm{start}(r)\\}$

can be viewed as $\\{1,\dots,2|\mathcal{X}|\\}$, where
$\mathrm{end}(r)\coloneqq 2r-1$ and $\mathrm{start}(x)\coloneqq 2r$. Thus, we
have the ordering
$\mathrm{end}(1)<\mathrm{start}(1)<\mathrm{end}(2)<\mathrm{start}(2)<\cdots<\mathrm{end}(|\mathcal{X}|)<\mathrm{start}(|\mathcal{X}|)$.
We define
$\mathcal{B}\coloneqq\bigcup_{r\in[|\mathcal{Y}|]}\\{\mathrm{end}(r),\mathrm{start}(r)\\}$
analogously.

We can now define a representation of $R_{i,j}(\lambda)$ in rank space as
follows: For any
$R_{i,j}(\lambda)=(a_{i,j}(\lambda),b_{i,j}(\lambda))\times(c_{i,j}(\lambda),d_{i,j}(\lambda))$,
we define its _closed rank representation_ $C_{i,j}(\lambda)$ as

$\displaystyle C_{i,j}(\lambda)\coloneqq$
$\displaystyle[\mathrm{start}(\max\mathrm{rank}_{\lambda}(a_{i,j}(\lambda))),\mathrm{end}(\min\mathrm{rank}_{\lambda}(b_{i,j}(\lambda)))]\times$
$\displaystyle[\mathrm{start}(\max\mathrm{rank}_{\lambda}(c_{i,j}(\lambda))),\mathrm{end}(\min\mathrm{rank}_{\lambda}(d_{i,j}(\lambda)))],$

where $\min$ and $\max$ are taken over intervals and evaluate to the start and
end, respectively.

The following lemma proves equivalence of the two representations.

######  Lemma 7.2.

Let $x,x^{\prime}\in\mathcal{X},y,y^{\prime}\in\mathcal{Y}$, as well as
$r=\min\mathrm{rank}_{\lambda}(x),r^{\prime}=\max\mathrm{rank}_{\lambda}(x^{\prime})$
and
$s=\min\mathrm{rank}_{\lambda}(y),s^{\prime}=\max\mathrm{rank}_{\lambda}(y^{\prime})$.
Then,

$\bigcup_{i,j}R_{i,j}(\lambda)\text{ covers
}[x,x^{\prime}]\times[y,y^{\prime}]\iff\bigcup_{i,j}C_{i,j}(\lambda)\text{
covers
}[\mathrm{end}(r),\mathrm{start}(r^{\prime})]\times[\mathrm{end}(s),\mathrm{start}(s^{\prime})].$

###### Proof.

Let $x=x_{1}<x_{2}<\dots<x_{R}=x^{\prime}$ denote the distinct values in
$\mathcal{X}\cap[x,x^{\prime}]$ under $\lambda$, and likewise let
$y=y_{1}<y_{2}<\dots<y_{S}=y^{\prime}$ denote the distinct values in
$\mathcal{Y}\cap[y,y^{\prime}]$ under $\lambda$. We partition
$[x,x^{\prime}]\times[y,y^{\prime}]$ into regions in
$\mathcal{I}\times\mathcal{J}$, where

$\displaystyle\mathcal{I}=\\{\\{x_{1}\\},(x_{1},x_{2}),\\{x_{2}\\},\dots,(x_{R-1},x_{R}),\\{x_{R}\\}\\}$
$\displaystyle\mathcal{J}=\\{\\{y_{1}\\},(y_{1},y_{2}),\\{y_{2}\\},\dots,(y_{S-1},y_{S}),\\{y_{S}\\}\\}$

To each interval of the form $\\{x_{i}\\}$, we associate the interval

$\\{\mathrm{end}(\min\mathrm{rank}_{\lambda}(x_{i})),\mathrm{start}(\max\mathrm{rank}_{\lambda}(x_{i}))\\},$

and to each interval of the form $(x_{i},x_{i+1})$, we associate the interval

$\\{\mathrm{start}(\max\mathrm{rank}_{\lambda}(x_{i})),\mathrm{end}(\min\mathrm{rank}_{\lambda}(x_{i+1}))\\},$

with the analogous associations for intervals in $\mathcal{J}$. The claim is
that each $\tau\in I\times J$ for $I\in\mathcal{I},J\in\mathcal{J}$ is covered
by $\bigcup_{i,j}R_{i,j}(\lambda)$ if and only if the Cartesian product of the
associated intervals is covered by $\bigcup_{i,j}C_{i,j}(\lambda)$. We show
the claim for the case that $I=\\{x_{k}\\},J=(y_{\ell},y_{\ell+1})$, all other
cases are analogous.

We have that

$\displaystyle\tau\in\\{x_{k}\\}\times(y_{\ell},y_{\ell+1})\text{ is covered
by }\bigcup_{i,j}R_{i,j}(\lambda)$ $\displaystyle\iff$ $\displaystyle\exists
i,j:R_{i,j}(\lambda)=(x_{a},x_{b})\times(y_{c},y_{d})\text{ with
}x_{a}<x_{k}<x_{b}\text{ and }y_{c}\leq y_{\ell}<y_{\ell+1}\leq y_{d}$
$\displaystyle\iff$ $\displaystyle\exists
i,j:C_{i,j}(\lambda)=[\mathrm{start}(a^{\prime}),\mathrm{end}(b^{\prime})]\times[\mathrm{start}(c^{\prime}),\mathrm{end}(d^{\prime})]\text{
with }$ $\displaystyle\qquad\qquad
a^{\prime}<\min\mathrm{rank}_{\lambda}(x_{k})\leq\max\mathrm{rank}_{\lambda}(x_{k})<b^{\prime},$
$\displaystyle\qquad\qquad
c^{\prime}\leq\min\mathrm{rank}_{\lambda}(y_{\ell})<\max\mathrm{rank}_{\lambda}(y_{\ell+1})\leq
d^{\prime}$ $\displaystyle\iff$
$\displaystyle\\{\mathrm{end}(\min\mathrm{rank}_{\lambda}(x_{k})),\mathrm{start}(\max\mathrm{rank}_{\lambda}(x_{k}))\\}$
$\displaystyle\times\\{\mathrm{start}(\max\mathrm{rank}_{\lambda}(y_{\ell})),\mathrm{end}(\min\mathrm{rank}_{\lambda}(y_{\ell+1}))\\}\text{
is covered by }\bigcup_{i,j}C_{i,j}(\lambda).$

where the last equivalence is notable, as it uses that all $C_{i,j}(\lambda)$
are of the form
$[\mathrm{start}(a^{\prime}),\mathrm{end}(b^{\prime})]\times[\mathrm{start}(c^{\prime}),\mathrm{end}(d^{\prime})]$.
∎

Thus, by checking whether the closed rectangles $C_{i,j}(\lambda)$ cover the
area corresponding to the bounding box $B$ of $Q$, we can determine whether
$\lambda$ is a feasible placement. To reduce this further to the question
whether $\bigcup_{i,j}C_{i,j}(\lambda)$ covers the full area
$[1,|\mathcal{A}|]\times[1,|\mathcal{B}|]$, we introduce four additional
rectangles $C_{L},C_{R},C_{T},C_{B}$ covering everything _but_ the bounding
box $B$:

$\displaystyle C_{L}$
$\displaystyle=[1,\mathrm{end}(\min\mathrm{rank}_{\lambda}(x_{0}^{B}))]\times[1,|\mathcal{B}|]$
$\displaystyle C_{R}$
$\displaystyle=[\mathrm{start}(\max\mathrm{rank}_{\lambda}(x_{1}^{B})),|\mathcal{A}|]\times[1,|\mathcal{B}|]$
$\displaystyle C_{B}$
$\displaystyle=[1,|\mathcal{A}|]\times[1,\mathrm{end}(\min\mathrm{rank}_{\lambda}(y_{0}^{B}))]$
$\displaystyle C_{T}$
$\displaystyle=[1,|\mathcal{A}|]\times[\mathrm{start}(\max\mathrm{rank}_{\lambda}(y_{1}^{B})),|\mathcal{B}|]$

Let
$\mathcal{C}_{\lambda}=(\bigcup_{i,j}C_{i,j}(\lambda))\cup\\{C_{L},C_{R},C_{B},C_{T}\\}$
denote the set of rectangles in our closed rank representation.

The main idea of our algorithm is to start from some value $\lambda_{0}$ that
trivially satisfies $\lambda_{0}>\lambda^{*}$, and decrease $\lambda$ while
maintaining a data structure for $\mathcal{C}_{\lambda}$ that after any change
allows us to check whether $\mathcal{C}_{\lambda}$ still covers the full space
$[1,|\mathcal{A}|]\times[1,|\mathcal{B}|]$. Thus, when does
$\mathcal{C}_{\lambda}$ change while $\lambda$ decreases?

Clearly, $\mathcal{C}_{\lambda}$ only changes when the sorted order of
$\mathcal{X}$ or $\mathcal{Y}$ changes, i.e., at an intersection point
$\lambda$ where $x(\lambda)=x^{\prime}(\lambda)$ for some
$x,x^{\prime}\in\mathcal{X}$ or $y(\lambda)=y^{\prime}(\lambda)$ for some
$y,y^{\prime}\in\mathcal{Y}$. Let $\lambda_{1}\geq\dots\geq\lambda_{L}$ denote
the descendingly sorted order of such $\lambda$, which we call _critical
values_. Since every $x\in\mathcal{X}$ and every $y\in\mathcal{Y}$ is a linear
(or constant) function in $\lambda$, we obtain that there are at most ${\cal
O}(|\mathcal{X}|^{2}+|\mathcal{Y}|^{2})={\cal O}((pq)^{2})$ such values. Note
that we can determine $\lambda_{1},\dots,\lambda_{L}$ in time ${\cal
O}((pq)^{2}\log pq)$.

The critical values $\lambda_{1},\dots,\lambda_{L}$ partition $\mathbb{R}$
into the regions

$(\infty,\lambda_{1}),\\{\lambda_{1}\\},(\lambda_{1},\lambda_{2}),\dots,\\{\lambda_{L}\\},(\lambda_{L},-\infty),$

where $C_{\lambda}$ is uniform (unchanged) in each
$(\lambda_{i},\lambda_{i+1})$. As is intuitively clear, $\lambda^{*}$ can only
be one of the critical values, formally proved below.

######  Proposition 7.2.

We must have $\lambda^{*}=\lambda_{i}$ for some $i\in[L]$.

###### Proof.

Consider a feasible translation $\tau$ for some scaling factor
$\lambda\in(\lambda_{i},\lambda_{i+1})$. Note that
$\tau\in[x_{a},x_{a+1}]\times[y_{b},y_{b+1}]$ for some indices $a,b$ in the
sorted orders of $\mathcal{X},\mathcal{Y}$ under $\lambda$. Observe that any
$\tau^{\prime}\in[x_{a},x_{a+1}]\times[y_{b},y_{b+1}]$ remains a feasible
translation for every $\lambda\in[\lambda_{i},\lambda_{i+1})$, in particular
for $\lambda=\lambda_{i}$: none of the open rectangles $R_{i,j}$ can cover any
point in $[x_{a},x_{a+1}]\times[y_{b},y_{b+1}]$, and this region remains non-
empty (but possibly consisting of a single point) for $\lambda=\lambda_{i}$. ∎

We can finally give the main outline of our algorithm, see Algorithm 1.

1:function LargestCopy($P$, $Q$)

2: Compute critical values $\lambda_{1}\geq\cdots\geq\lambda_{L}$

3: Compute $\mathcal{C}\leftarrow\mathcal{C}_{\lambda}$ for
$\lambda\in(\infty,\lambda_{1})$.

4: for $i\leftarrow 1$ to $L$ do

5: Update $\mathcal{C}$ to $\mathcal{C}_{\lambda}$ for $\lambda=\lambda_{i}$

6: if $\mathcal{C}$ does not fully cover
$[1,|\mathcal{A}|]\times[1,|\mathcal{B}|]$ then

7: return $\lambda_{i}$

8: Update $\mathcal{C}$ to $\mathcal{C}_{\lambda}$ for
$\lambda\in(\lambda_{i},\lambda_{i+1})$

Algorithm 1 Computing $\lambda^{*}$, the largest scaling factor $\lambda$ such
that $\lambda P$ can be translated to be contained in $Q$

We now show that Algorithm 1 fulfills the requirements of Lemma 7.1.

###### Proof of Lemma 7.1.

By Proposition 7.2 and Lemma 7.2, correctness of Algorithm 1 is immediate. It
remains to argue how we can implement this algorithm to achieve the desired
upper bound. As noted above, computing the sorted critical values
$\lambda_{1},\dots,\lambda_{L}$ takes time ${\cal O}((pq)^{2}\log pq)$.
Afterwards, we need to maintain a data structure for $\mathcal{C}$ such that
we can answer whether $\mathcal{C}$ fully covers
$[1,|\mathcal{A}|]\times[1,|\mathcal{B}|]$. Observe that any changes to
$C_{i,j}(\lambda)$ or $C_{L},C_{R},C_{B},C_{H}$ occur at some critical value
$\lambda_{\ell}$. Specifically, a coordinate of $C_{i,j}(\lambda)$ changes
only if $a_{i,j}(\lambda)$ or $b_{i,j}(\lambda)$ (respectively,
$c_{i,j}(\lambda)$ or $d_{i,j}(\lambda)$) is equal to some other $x(\lambda)$
for some $x\in\mathcal{X}$ (respectively $y(\lambda)$ for some
$y\in\mathcal{Y}$) — note that the corresponding value will undergo at most
two changes, one at $\lambda=\lambda_{i}$ (where it is equal to other
coordinates) and one for $(\lambda_{i},\lambda_{i+1})$ (between critical
values, all coordinates are indeed distinct). Similarly, any change to
$C_{L},C_{R},C_{B},C_{T}$ only occurs if under $\lambda$ there is equality of
$x_{0}^{B}$ or $x_{1}^{B}$ with some other $x\in\mathcal{X}$, or of
$y_{0}^{B}$ or $y_{1}^{B}$ with some other $y\in\mathcal{Y}$. By charging each
update to a pair $(x,x^{\prime})\in\mathcal{X}^{2}$ or
$(y,y^{\prime})\in\mathcal{Y}^{2}$ responsible for the update (resulting from
$x(\lambda)=x^{\prime}(\lambda)$ or $y(\lambda)=y^{\prime}(\lambda)$), we can
bound the total number of updates to $\mathcal{C}$ by ${\cal
O}(|\mathcal{X}|^{2}+|\mathcal{Y}|^{2})={\cal O}((pq)^{2})$, as each pair
$(x,x^{\prime})$ or $(y,y^{\prime})$ is charged at most a constant number of
times and either satisfies $x(\lambda)=x^{\prime}(\lambda)$ or
$y(\lambda)=y^{\prime}(\lambda)$ for all $\lambda$ (and thus is responsible
for no updates) or has a unique point of equality (since each
$x\in\mathcal{X}$ and $y\in\mathcal{Y}$ is a linear function in $\lambda$).

In total, we perform $U={\cal O}((pq)^{2})$ many updates to $\mathcal{C}$.
Observe that we can precompute these updates in such a way that we search for
the first update after which the collection $\mathcal{C}$ of rectangles no
longer covers the full region
$[1,|\mathcal{A}|]\times[1,|\mathcal{B}|]$.101010The very observant reader
might notice that there is a slight technicality: at each update in Lines 5
and 8, we should first add all new boxes before we delete old boxes in order
to not create artificial holes while updating. Note however, that this results
in having, at any given time, only at most twice as many boxes in our data
structure compared to the initial promise of $p^{\prime}q^{\prime}+4$ boxes.
Thus, using a data structure for Offline Dynamic Rectangle Cover, we can
simulate Algorithm 1 in time ${\cal O}((pq)^{2}\log(pq)+T(pq,(pq)^{2}))$. ∎

## References

  * [AAS98] Pankaj K. Agarwal, Nina Amenta, and Micha Sharir.  Largest placement of one convex polygon inside another.  Discret. Comput. Geom., 19(1):95–104, 1998.
  * [AAS99] Pankaj K. Agarwal, Boris Aronov, and Micha Sharir.  Motion planning for a convex polygon in a polygonal environment.  Discret. Comput. Geom., 22(2):201–221, 1999.
  * [AB89] Francis Avnaim and Jean-Daniel Boissonnat.  Polygon placement under translation and rotation.  RAIRO Theor. Informatics Appl., 23(1):5–28, 1989.
  * [ABBK17] Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann.  Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’17), pages 192–203. IEEE Computer Society, 2017.
  * [ABBK20] Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann.  Impossibility results for grammar-compressed linear algebra.  In Proc. 33rd Advances in Neural Information Processing Systems (NeurIPS 2020), 2020.
  * [AFH02] Pankaj K. Agarwal, Eyal Flato, and Dan Halperin.  Polygon decomposition for efficient construction of minkowski sums.  Comput. Geom., 21(1-2):39–61, 2002.
  * [AG95] Helmut Alt and Michael Godau.  Computing the Fréchet distance between two polygonal curves.  Internat. J. Comput. Geom. Appl., 5(1–2):78–99, 1995.
  * [AL13] Amir Abboud and Kevin Lewi.  Exact weight subgraphs and the k-sum conjecture.  In Proc. 40th International Colloquium on Automata, Languages, and Programming (ICALP ’13), volume 7965 of Lecture Notes in Computer Science, pages 1–12. Springer, 2013.
  * [AS98] Pankaj K. Agarwal and Micha Sharir.  Efficient algorithms for geometric optimization.  ACM Comput. Surv., 30(4):412–458, 1998.
  * [AVW21] Amir Abboud and Virginia Vassilevska Williams.  Fine-grained hardness for edit distance to a fixed sequence.  In Proc. 48th International Colloquium on Automata, Languages, and Programming (ICALP ’21), volume 198 of LIPIcs, pages 7:1–7:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [BFM86] Brenda S. Baker, Steven Fortune, and Stephen R. Mahaney.  Polygon containment under translation.  J. Algorithms, 7(4):532–548, 1986.
  * [BH01] Gill Barequet and Sariel Har-Peled.  Polygon containment and translational min-hausdorff-distance between segment sets are 3sum-hard.  Int. J. Comput. Geom. Appl., 11(4):465–474, 2001.
  * [BK15] Karl Bringmann and Marvin Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’15), pages 79–97. IEEE Computer Society, 2015.
  * [BKN21] Karl Bringmann, Marvin Künnemann, and André Nusser.  Discrete Fréchet distance under translation: Conditional hardness and an improved algorithm.  ACM Trans. Algorithms, 17(3):25:1–25:42, 2021.
  * [BN21] Karl Bringmann and André Nusser.  Translating hausdorff is hard: Fine-grained lower bounds for hausdorff distance under translation.  In Proc. 37th International Symposium on Computational Geometry (SoCG ’21), volume 189 of LIPIcs, pages 18:1–18:17. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2021.
  * [Cha83] Bernard Chazelle.  The polygon containment problem.  Advances in Computing Research, pages 1–33, 1983.
  * [Cha10] Timothy M. Chan.  A (slightly) faster algorithm for Klee’s measure problem.  Comput. Geom., 43(3):243–250, 2010.
  * [CK92] L. Paul Chew and Klara Kedem.  Improvements on geometric pattern matching problems.  In Proc. 3rd Algorithm Theory Scandinavian Workshop on Algorithm Theory (SWAT ’92), volume 621 of Lecture Notes in Computer Science, pages 318–325. Springer, 1992.
  * [CK93] L. Paul Chew and Klara Kedem.  A convex polygon among polygonal obstacles: Placement and high-clearance motion.  Comput. Geom., 3:59–89, 1993.
  * [DGS20] Bartlomiej Dudek, Pawel Gawrychowski, and Tatiana Starikovskaya.  All non-trivial variants of 3-ldt are equivalent.  In Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC ’20), pages 974–981. ACM, 2020.
  * [EM94] Thomas Eiter and Heikki Mannila.  Computing discrete Fréchet distance.  Technical Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994.
  * [Eri99] Jeff Erickson.  New lower bounds for convex hull problems in odd dimensions.  SIAM J. Comput., 28(4):1198–1214, 1999.
  * [For85] Steven Fortune.  A fast algorithm for polygon containment by translation (extended abstract).  In Proc. 12th International Colloquium on Automata, Languages and Programming (ICALP ’85), volume 194 of Lecture Notes in Computer Science, pages 189–198. Springer, 1985.
  * [GO95] Anka Gajentaan and Mark H. Overmars.  On a class of $O(n^{2})$ problems in computational geometry.  Comput. Geom. Theory Appl., 5(3):165–185, 1995.
  * [Her96] Antonio Hernández-Barrera.  Algorithms for deciding the containment of polygons.  Inf. Process. Lett., 59(5):261–265, 1996.
  * [LS87] Daniel Leven and Micha Sharir.  Planning a purely translational motion for a convex object in two-dimensional space using generalized voronoi diagrams.  Discret. Comput. Geom., 2:9–31, 1987.
  * [OST17] Joseph O’Rourke, Subhash Suri, and Csaba D. Tóth.  Polygons.  In Jacob E. Goodman, Joseph O’Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, Third Edition, pages 787–810. CRC Press LLC, 2017.
  * [OY91] Mark H. Overmars and Chee-Keng Yap.  New upper bounds in Klee’s measure problem.  SIAM J. Comput., 20(6):1034–1045, 1991.
  * [ST94] Micha Sharir and Sivan Toledo.  Extremal polygon containment problems.  Comput. Geom., 4:99–118, 1994.
  * [VW18] Virginia Vassilevska Williams.  On some fine-grained questions in algorithms and complexity.  In Proceedings of the International Congress of Mathematicians, ICM ’18, pages 3447–3487, 2018.
  * [Wen02] Carola Wenk.  Shape matching in higher dimensions.  PhD thesis, Freie Universität Berlin, 2002.  PhD Thesis.
  * [Wil05] Ryan Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theoretical Computer Science, 348(2-3):357–365, 2005.