# Convex Polygon Containment:
Improving Quadratic to Near Linear Time

Timothy M. Chan Department of Computer Science, University of Illinois at
Urbana-Champaign (tmc@illinois.edu). Work supported in part by NSF Grant
CCF-2224271. Isaac M. Hair Department of Computer Science, University of
California, Santa Barbara (hair@ucsb.edu).

###### Abstract

We revisit a standard polygon containment problem: given a convex $k$-gon $P$
and a convex $n$-gon $Q$ in the plane, find a placement of $P$ inside $Q$
under translation and rotation (if it exists), or more generally, find the
largest copy of $P$ inside $Q$ under translation, rotation, and scaling.

Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal,
Amenta, and Sharir (1998) all required $\Omega(n^{2})$ time, even in the
simplest $k=3$ case. We present a significantly faster new algorithm for $k=3$
achieving $O(n\mathop{\rm polylog}n)$ running time. Moreover, we extend the
result for general $k$, achieving $O(k^{O(1/\varepsilon)}n^{1+\varepsilon})$
running time for any $\varepsilon>0$.

Along the way, we also prove a new $O(k^{O(1)}n\mathop{\rm polylog}n)$ bound
on the number of similar copies of $P$ inside $Q$ that have 4 vertices of $P$
in contact with the boundary of $Q$ (assuming general position input),
disproving a conjecture by Agarwal, Amenta, and Sharir (1998).

##  1 Introduction

_Polygon containment_ problems have been studied since the early years of
computational geometry [1, 2, 6, 9, 12, 13, 14, 16, 17, 20, 22, 24, 25, 26,
27, 30]. In this paper, we focus on two of the most fundamental versions of
the problem for convex polygons:

######  Problem 1.

Given a convex $k$-gon $P$ and a convex $n$-gon $Q$ in $\mathbb{R}^{2}$, (i)
find a congruent copy of $P$ inside $Q$ (if it exists); or more generally,
(ii) find the largest similar copy of $P$ inside $Q$.

In a congruent copy, we allow translation and rotation; in a similar copy, we
allow translation, rotation, and scaling. Rotation is what makes the problem
challenging, as the corresponding problem without rotation can be solved in
linear time by a simple reduction to linear programming in 3 variables [30].

There were 3 key prior papers on this problem:

  1. 1.

In 1983, Chazelle [12] initiated the study of polygon containment problems and
presented an $O(kn^{2})$-time algorithm specifically for Problem 1(i). In
particular, an entire section of his paper was devoted to an $O(n^{2})$-time
algorithm just for the $k=3$ (triangle) case.

  2. 2.

Sharir and Toledo [30] (preliminary version in SoCG’91) applied parametric
search [23] to reduce various versions of “extremal” polygon containment
problems (about finding largest copies) to their corresponding decision
problems. In particular, they described an $O(n^{2}\log^{2}n)$-time algorithm
for Problem 1(ii) in the $k=3$ case.

  3. 3.

In 1998, Agarwal, Amenta, and Sharir [1] studied Problem 1(ii) and obtained an
$O(kn^{2}\log n)$-time algorithm. Their approach is to explore the entire
solution space. More precisely, consider a standard 4-parameter representation
of similarity transformations [7]: given $(s,t,u,v)\in\mathbb{R}^{4}$, let
$\varphi_{s,t,u,v}:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ be the similarity
transformation $(x,y)\mapsto(sx-ty+u,tx+sy+v)$, which has scaling factor
$\sqrt{s^{2}+t^{2}}$. The region

${\cal P}=\\{(s,t,u,v)\in\mathbb{R}^{4}:\ \mbox{$\varphi_{s,t,u,v}(p)\in Q$
for all vertexes $p$ of $P$}\\}$

describes all feasible solutions and is an intersection of $O(kn)$ halfspaces
in $\mathbb{R}^{4}$ (since $\varphi_{s,t,u,v}(p)$ is a linear function in the
4 variables $s,t,u,v$ for any fixed point $p$). The problem is to find a point
in ${\cal P}$ maximizing the convex function $s^{2}+t^{2}$ (the optimum must
be located at a vertex). By standard results, a 4-polytope with $O(kn)$ facets
has $O(k^{2}n^{2})$ combinatorial complexity (and can be constructed in
$O(k^{2}n^{2})$ time) [28]. Agarwal, Amenta, and Sharir improved the
combinatorial bound to $O(kn^{2})$ for this particular polytope ${\cal P}$,
enabling them to derive an algorithm with a similar time bound.

Notice that all these previous algorithms have $\Omega(n^{2})$ time
complexity, even in the triangle ($k=3$) case. (Other quadratic algorithms for
$k=3$ have been found, e.g., mostly recently by Lee, Eom, and Ahn [22].) To
explain why, Chazelle [12] mentioned that there are input convex polygons $Q$
for which the number of different “stable solutions” is $\Omega(n^{2})$.
(Other authors made similar observations [22].) More generally, Agarwal,
Amenta, and Sharir [1] exhibited a construction of input convex polygons $P$
and $Q$ for which the polytope ${\cal P}$ has complexity $\Omega(kn^{2})$,
matching their combinatorial upper bound.

Although such combinatorial lower bound results do not technically rule out
the possibility of faster algorithms that find an optimal solution without
generating the entire solution space, they indicate that quadratic complexity
is a natural barrier. In general, no techniques are known to maximize a convex
function in an intersection of halfspaces in constant dimensions with worst-
case time better than constructing the entire halfspace intersection.

What motivates us to revisit this topic is the similarity of the $k=3$ problem
to the well-known _3SUM problem_ (in the sense that the main case of the
triangle problem is about finding a _triple_ of vertices/edges of $Q$ in
contact with the triangle $P$). Our initial thought is to apply the exciting
recent advances for 3SUM and related problems [5, 8, 11, 18, 19] to design
decision trees with subquadratic height. This would potentially lead to
slightly subquadratic algorithms with running time of the form
$n^{2}/\mathop{\rm polylog}n$.

Although we believe this line of attack can indeed be applied to Problem 1 in
the $k=3$ case, the improvement in the time complexity would be tiny, and
generalization to $k>3$ is unclear. Furthermore, the usage of such heavy
machinery might seem premature and unjustified since the $k=3$ problem has not
been shown to be 3SUM-hard. Barequet and Har-Peled [9] proved that Problem
1(i) for convex polygons is 3SUM-hard when $k=n$ and so has a near-quadratic
conditional lower bound, but for $k=n$, the current upper bound is cubic. More
recently, Künnemann and Nusser [20] have obtained conditional lower bounds for
a number of other polygon containment problems, but not in the convex cases.

#### New results.

In this paper, we not only truly break the quadratic barrier but also discover
a near-linear, $O(n\mathop{\rm polylog}n)$-time algorithm for Problem 1(ii) in
the $k=3$ case! This represents a substantial improvement over the previous
algorithms from multiple decades earlier, and directly addresses an open
problem posed by Agarwal, Amenta, and Sharir [1] asking for an algorithm
faster than $\Theta(kn^{2})$ time. (We cannot think of too many classical 2D
problems in computational geometry of comparable stature where
quadratic/superquadratic time complexity is reduced to near-linear in a single
swoop after a long gap. The closest analog is perhaps Sharir’s breakthrough
$O(n\mathop{\rm polylog}n)$-time algorithm for the 2D Euclidean 2-center
problem [29] that improved a string of previous $O(n^{2}\mathop{\rm
polylog}n)$-time algorithms.)

Furthermore, we generalize our approach and obtain an
$O(n^{1+\varepsilon})$-time algorithm for Problem 1(ii) for any constant
$k>3$, where $\varepsilon>0$ is an arbitrarily small constant. For non-
constant $k\leq n$, the time bound is
$O(k^{O(1/\varepsilon)}n^{1+\varepsilon})$ for any choice of (possibly non-
constant) $\varepsilon>0$. (By choosing $\varepsilon=\sqrt{\log k/\log n}$,
the bound can be rewritten as $n2^{O(\sqrt{\log k\log n})}$.) This beats the
previous $O(kn^{2})$ bound for all $k<n^{\alpha}$ for some concrete constant
$\alpha>0$.

#### New approach.

Although Problem 1(ii) reduces to Problem 1(i) by parametric search [23, 30]
(if one does not mind extra logarithmic factors), we actually find it more
convenient to solve Problem 1(ii) directly (i.e., find the largest copy). The
optimal solution must belong to one of the following cases, as observed in
previous works (by simple direct arguments, or by recalling that the optimum
corresponds to a vertex of the 4-polytope ${\cal P}$):

  * •

2-Contact (i.e., 2-Anchor) Case: 2 distinct vertices of $P$ are in contact
with $\partial Q$, both of which are at 2 vertices of $Q$. These 2 vertices of
$P$ are called the 2 “anchor” vertices.

  * •

3-Contact (i.e., 1-Anchor) Case: 3 distinct vertices of $P$ are in contact
with $\partial Q$, one at a vertex of $Q$ and the other two on edges of $Q$.
The vertex of $P$ placed at a vertex of $Q$ is referred to as the “anchor”
vertex.

  * •

4-Contact (i.e., No-Anchor) Case: 4 distinct vertices of $P$ are in contact
with $\partial Q$, all on edges of $Q$.

For $k=3$, the main case is the 3-contact case, since it turns out that the
2-contact case can be solved in a similar way (and the 4-contact case, of
course, does not arise). The overall strategy is to divide into sub-problems
involving different “arcs” (i.e., contiguous pieces) of $\partial Q$. Our key
observation is that under certain conditions about the slopes/angles of the
input arcs, all 3-contact feasible solutions may be covered by just a linear
number of pairs of sub-edges, due to _monotonicity_ arguments—this is despite
the fact that the total number of 3-contact solutions may be quadratic. In
such scenarios, we can search for the best solution by using standard
geometric data structuring techniques (concerning intersections of ellipses,
as it turns out). A simple binary divide-and-conquer reduces to instances
where such conditions are met, resulting in an $O(n\mathop{\rm
polylog}n)$-time algorithm.

For $k>3$, extending the 3-contact algorithm requires more technical effort
(and a slightly increased running time), but what appears even more
challenging is the 4-contact case. The lack of anchor vertices seems to make
everything more complicated (including the needed geometric data structures).
However, with a different strategy, we show surprisingly that the 4-contact
case is easier in the sense that the total number of 4-contact feasible
solutions is actually near-linear in $n$, namely, $O(k^{4}n\mathop{\rm
polylog}n)$ (assuming general position input). Thus, we can afford to
enumerate them all! We prove this combinatorial bound by running our $k=3$
algorithm on different triples of vertices of $P$ and then piecing information
together via further interesting monotonicity arguments.

To see how counterintuitive our near-linear combinatorial bound for 4-contact
solutions is, recall that Agarwal, Amenta, and Sharir [1] proved an
$\Omega(kn^{2})$ lower bound on the size of the solution space. They noted
that their construction only lower-bounded the number of 3-contact solutions,
and at the end of their paper, they asked for another construction with
$\Omega(kn^{2})$ 4-contact solutions. Our proof answers their question in the
negative.

#### Preliminaries.

The _angle_ of a line $\overleftrightarrow{p_{1}p_{2}}$, denoted
$\theta_{p_{1}p_{2}}$, refers to the angle measured counterclockwise (ccw)
from the $x$-axis to $\overleftrightarrow{p_{1}p_{2}}$. (Note that
$\theta_{p_{1}p_{2}}\in[0,\pi)$ and
$\theta_{p_{2}p_{1}}=\theta_{p_{1}p_{2}}$.) An _arc_ $\Gamma$ of a convex
polygon $Q$ refers to a contiguous portion of the boundary $\partial Q$ whose
supporting lines have angles in an interval of length $<\pi/3$. Let
$\Lambda(\Gamma)$ (the _angle range_ of $\Gamma$) denote the interval
containing the angles of all supporting lines of $\Gamma$. We allow
$\Lambda(\Gamma)$ to wrap around (mod $\pi$), so $[a,b]$ indicates
$[a,\pi)\cup[0,b]$ if $a>b$. We assume that no polygons contain parallel
adjacent edges, as any such edges can be merged.

We assume that all polygon boundaries and their edges/arcs are oriented in ccw
order. For each edge $e$ of $Q$, let $\overleftrightarrow{e}$ denote its
extension as an oriented line (with $Q$ on its “left” side). For an arc
$\Gamma$, let $\overleftrightarrow{\Gamma}$ denote an extension of $\Gamma$
where the first and last edge are extended to rays (again oriented with $Q$ on
its “left” side). We use $\widetilde{O}$ notation to hide $\mathop{\rm
polylog}n$ factors.

##  2 3-Contact (1-Anchor) Case

In this section, we solve the 3-contact case, where there is 1 anchor vertex
$p_{1}$ of $P$. We will first present an algorithm for $k=3$ (when $P$ is a
triangle), and then we discuss how to generalize it for $k>3$. We will divide
into sub-problems operating on different arcs. For $k=3$, the goal is to find
a placement where the anchor $p_{1}$ is at a vertex on an arc $\Gamma_{1}$,
and the two other vertices $p_{2}$ and $p_{3}$ of $P$ are on edges of arcs
$\Gamma_{2}$ and $\Gamma_{3}$.

###  2.1 An Easy “Disjoint” Case for $k=3$

We begin with an easy lemma to handle the case when the angle ranges for
$\Gamma_{2}$ and $\Gamma_{3}$, after suitable rotational shifts, are disjoint.

Figure 1: The construction from Lemma 1. Each dashed triangle is a similar
copy of $\triangle p_{1}p_{2}p_{3}$, and the purple arc is
$f_{v_{1}}(\Gamma_{3})$. (We draw $\Gamma_{2}$ and $\Gamma_{3}$ instead of
$\overleftrightarrow{\Gamma_{2}}$ and $\overleftrightarrow{\Gamma_{3}}$ for
visual clarity.)

######  Lemma 1.

Let $\triangle p_{1}p_{2}p_{3}$ be a triangle. Let
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be arcs of a convex $n$-gon $Q$, such that

  * •

$\Lambda(\Gamma_{2})+\theta_{p_{1}p_{3}}$ and
$\Lambda(\Gamma_{3})+\theta_{p_{1}p_{2}}$ are disjoint (mod $\pi$).

In $\widetilde{O}(|\Gamma_{1}|)$ time, we can compute, for each vertex $v_{1}$
of $\Gamma_{1}$, a point $X(v_{1})$ on $\Gamma_{2}$ and a sub-arc $I(v_{1})$
of $\Gamma_{2}$, satisfying the following property:111We allow $X(v_{1})$ to
be undefined and $I(v_{1})$ to be empty.

> For every similarity transformation $\varphi$ that has $\varphi(p_{1})$
> being a vertex $v_{1}$ of $\Gamma_{1}$ and $\varphi(p_{2})$ on $\Gamma_{2}$,
> we have: (i) $\varphi(p_{3})$ is on $\Gamma_{3}$ iff
> $\varphi(p_{2})=X(v_{1})$, and (ii) $\varphi(p_{3})$ is left of
> $\overleftrightarrow{\Gamma_{3}}$ iff $\varphi(p_{2})$ is on $I(v_{1})$.

###### Proof.

Let $f_{v_{1}}(\zeta)$ be the point $\varphi(p_{2})$ for the unique similarity
transformation $\varphi$ with $\varphi(p_{1})=v_{1}$ and
$\varphi(p_{3})=\zeta$. In other words, $f_{v_{1}}$ is a similarity
transformation that keeps $v_{1}$ fixed and sends $p_{3}$ to $p_{2}$, i.e., we
rotate around $v_{1}$ by an angle
$\theta_{p_{1}p_{2}}-\theta_{p_{1}p_{3}}+\\{0,\pm\pi\\}$, and scale by factor
$\|p_{1}-p_{2}\|/\|p_{1}-p_{3}\|$. Thus, $f_{v_{1}}(\Gamma_{3})$ is a similar
copy of $\Gamma_{3}$. The supporting lines for $f_{v_{1}}(\Gamma_{3})$ have
angles in
$\Lambda(\Gamma_{3})+\theta_{p_{1}p_{2}}-\theta_{p_{1}p_{3}}+\\{0,\pm\pi\\}$,
which by the assumption is disjoint from $\Lambda(\Gamma_{2})$ (mod $\pi$).
Thus,222 This is analogous to the fact that if $f$ and $g$ are functions over
$\mathbb{R}$ where the ranges of their derivatives $f^{\prime}$ and
$g^{\prime}$ are contained in two disjoint closed intervals, then $f$ and $g$
intersect once.  $f_{v_{1}}(\overleftrightarrow{\Gamma_{3}})$ and
$\overleftrightarrow{\Gamma_{2}}$ intersect once, at a unique point $\nu$,
which we define as $X(v_{1})$, and which can be computed by binary search (see
Figure 1). We can define $I(v_{1})$ to be a prefix or suffix of $\Gamma_{2}$
delimited by $X(v_{1})$. ∎

Thus, to solve the 3-contact problem for $k=3$, we can just examine the unique
similarity transformation $\varphi$ with $\varphi(p_{1})=v_{1}$ and
$\varphi(p_{2})=X(v_{1})$ for each vertex $v_{1}$ of $\Gamma_{1}$, in near-
linear total time (assuming the disjointness condition is met). It suffices to
consider only this single similarity transformation for each
$v_{1}\in\Gamma_{1}$, since this is the only possible 3-contact placement.

###  2.2 A “Double-Disjoint” Case for $k=3$

Next, we address a different case where the angle ranges for $\Gamma_{1}$ and
$\Gamma_{2}$ are disjoint and the angle ranges for $\Gamma_{1}$ and
$\Gamma_{3}$ are disjoint, after appropriate rotational shifts. The following
lemma reveals a crucial monotonicity phenomenon that we will repeatedly
exploit.

To state the lemma, we first introduce some definitions: For two arcs
$\Gamma_{1}$ and $\Gamma_{2}$, a _pairing_ $M$ between $\Gamma_{1}$ and
$\Gamma_{2}$ refers to a subdivision of the (straight) edges of $\Gamma_{1}$
and $\Gamma_{2}$ into sub-edges, together with a bijective mapping between the
sub-edges of $\Gamma_{1}$ and the sub-edges of $\Gamma_{2}$. For a sub-edge
$e_{1}$ of $\Gamma_{1}$, we use $M(e_{1})$ to denote $e_{1}$’s corresponding
sub-edge in $\Gamma_{2}$; similarly, for a sub-edge $e_{2}$ of $\Gamma_{2}$,
we use $M(e_{2})$ to denote $e_{2}$’s corresponding sub-edge in $\Gamma_{1}$.
We say that the pairing $M$ is _monotonically increasing (resp. decreasing)_
if $M(e_{1})$ always advances in ccw (resp. cw) order in $\Gamma_{2}$ as
$e_{1}$ advances in ccw order in $\Gamma_{1}$ (see Figure 2).

Figure 2: (Left) Monotonically increasing pairing. (Right) Monotonically
decreasing pairing.

######  Lemma 2.

_(Pairing Lemma)_ Let $\triangle p_{1}p_{2}p_{3}$ be a triangle. Let
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be arcs of a convex $n$-gon $Q$, such that

  1. 1.

$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}$ and
$\Lambda(\Gamma_{2})+\theta_{p_{1}p_{3}}$ are disjoint (mod $\pi$), and

  2. 2.

$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}$ and
$\Lambda(\Gamma_{3})+\theta_{p_{1}p_{2}}$ are disjoint (mod $\pi$).

In $\widetilde{O}(n)$ time, we can compute a (monotonically increasing or
decreasing) pairing $M$ between $\Gamma_{2}$ and $\Gamma_{3}$ with $O(n)$ sub-
edges, satisfying the following property:

> For every similarity transformation $\varphi$ that has $\varphi(p_{1})$ on
> $\Gamma_{1}$ and $\varphi(p_{2})$ on a sub-edge $e_{2}$ of $\Gamma_{2}$, we
> have: (i) $\varphi(p_{3})$ is on $\Gamma_{3}$ iff $\varphi(p_{3})$ is on
> $M(e_{2})$; and (ii) $\varphi(p_{3})$ is left of
> $\overleftrightarrow{\Gamma_{3}}$ iff $\varphi(p_{3})$ is left of
> $\overleftrightarrow{M(e_{2})}$.

###### Proof.

We _match_ a point $\mu$ on $\overleftrightarrow{\Gamma_{2}}$ with a point
$\nu$ on $\overleftrightarrow{\Gamma_{3}}$ iff there exists a similarity
transformation $\varphi$ with $\varphi(p_{2})=\mu$, $\varphi(p_{1})$ on
$\overleftrightarrow{\Gamma_{1}}$, and $\varphi(p_{3})=\nu$.

Observe that a point $\mu$ on $\overleftrightarrow{\Gamma_{2}}$ matches a
unique point $\nu$ on $\overleftrightarrow{\Gamma_{3}}$. To see this, let
$f_{\mu}(\zeta)$ be the point $\varphi(p_{3})$ for the unique similarity
transformation $\varphi$ with $\varphi(p_{2})=\mu$ and $\varphi(p_{1})=\zeta$.
In other words, $f_{\mu}$ is the similarity transformation that keeps $\mu$
fixed and sends $p_{1}$ to $p_{3}$, i.e., we rotate around $\mu$ by an angle
$\theta_{p_{2}p_{3}}-\theta_{p_{2}p_{1}}+\\{0,\pm\pi\\}$, and scale by factor
$\|p_{3}-p_{2}\|/\|p_{1}-p_{2}\|$. Thus, $f_{\mu}(\Gamma_{1})$ is a similar
copy of $\Gamma_{1}$. The supporting lines for $f_{\mu}(\Gamma_{1})$ have
angles in
$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}-\theta_{p_{2}p_{1}}+\\{0,\pm\pi\\}$,
which by assumption 2 is disjoint from $\Lambda(\Gamma_{3})$ (mod $\pi$).
Thus, $f_{\mu}(\overleftrightarrow{\Gamma_{1}})$ and
$\overleftrightarrow{\Gamma_{3}}$ intersect once, namely, at the unique point
$\nu$. A symmetric argument (swapping subscripts 2 and 3) shows that a point
$\nu$ on $\overleftrightarrow{\Gamma_{3}}$ matches a unique point $\mu$ on
$\overleftrightarrow{\Gamma_{2}}$, this time, by assumption 1.

Consequently,333This is analogous to the fact that a continuous bijective
function over $\mathbb{R}$ must be monotone.  as $\mu$ moves along
$\overleftrightarrow{\Gamma_{2}}$, its matching point $\nu$ moves
monotonically along $\overleftrightarrow{\Gamma_{3}}$. We break an edge at the
points $\mu$ on $\Gamma_{2}$ that match the vertices of
$\overleftrightarrow{\Gamma_{3}}$, which can be found by $n$ binary searches.
Similarly, we break an edge at the points $\nu$ on $\Gamma_{3}$ that match the
vertices of $\overleftrightarrow{\Gamma_{3}}$, which can be found by $n$
binary searches. As a result, all points $\mu$ on a common sub-edge $e_{2}$ of
$\overleftrightarrow{\Gamma_{2}}$ are matched with points on a common sub-edge
of $\overleftrightarrow{\Gamma_{3}}$, which we define as $M(e_{2})$. For all
these points $\mu$, we have $f_{\mu}(\overleftrightarrow{\Gamma_{1}})$
intersecting this sub-edge $M(e_{2})$ of $\overleftrightarrow{\Gamma_{3}}$.
Also, for all $\zeta\in\Gamma_{1}$, $f_{\mu}(\zeta)$ is left of
$\overleftrightarrow{\Gamma_{3}}$ iff $f_{\mu}(\zeta)$ is left of
$\overleftrightarrow{M(e_{2})}$ (see Figure 3). ∎

Figure 3: An example of a pairing. Each dashed triangle is a similar copy of
$\triangle p_{1}p_{2}p_{3}$.

In the above, we did not claim a monotone pairing between $\Gamma_{2}$ and
$\Gamma_{1}$, nor between $\Gamma_{1}$ and $\Gamma_{3}$. Otherwise, we would
get a linear upper bound on the number of 3-contact solutions in this case,
which by our subsequent divide-and-conquer algorithm would yield an $O(n\log
n)$ bound on the number of 3-contact solutions in general for $k=3$,
contradicting the known quadratic lower bound [1, 22]! This contradiction does
not arise since in the worst case, each matched pair from $\Gamma_{2}$ and
$\Gamma_{3}$ could admit legal 3-contact placements with _every_ vertex of
$\Gamma_{1}$.

With the Pairing Lemma at hand, we can efficiently solve the problem when the
two disjointness conditions are met. Specifically, we set up a range searching
sub-problem between the $O(n)$ pairs of sub-edges in $\Gamma_{2}$ and
$\Gamma_{3}$ (the “data set”), and the $O(n)$ vertices of $\Gamma_{1}$ (the
“query points”). This range searching sub-problem turns out to be near-linear-
time solvable:

######  Lemma 3.

Let $\triangle p_{1}p_{2}p_{3}$ be a triangle. Let
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be arcs of a convex $n$-gon $Q$, such that

  1. 1.

$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}$ and
$\Lambda(\Gamma_{2})+\theta_{p_{1}p_{3}}$ are disjoint (mod $\pi$), and

  2. 2.

$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}$ and
$\Lambda(\Gamma_{3})+\theta_{p_{1}p_{2}}$ are disjoint (mod $\pi$).

In $\widetilde{O}(n)$ time, we can find a similarity transformation $\varphi$,
maximizing the scaling factor, such that $\varphi(p_{1})$ is a vertex of
$\Gamma_{1}$, $\varphi(p_{2})$ is on $\Gamma_{2}$, and $\varphi(p_{3})$ is on
$\Gamma_{3}$.

###### Proof.

Given $(s,t,u,v)\in\mathbb{R}^{4}$, let
$\varphi_{s,t,u,v}:\mathbb{R}^{2}\rightarrow\mathbb{R}^{2}$ be the similarity
transformation $(x,y)\mapsto(sx-ty+u,tx+sy+v)$ (which has scaling factor
$\sqrt{s^{2}+t^{2}}$).

Apply Lemma 2 to get a pairing $M$ between $\Gamma_{2}$ and $\Gamma_{3}$. For
each sub-edge $e_{2}$ of $\Gamma_{2}$, define

$\begin{array}[]{rrl}{\cal P}(e_{2})\
=&\\{(s,t,u,v)\in\mathbb{R}^{4}:&\mbox{$\varphi_{s,t,u,v}(p_{2})$ is on
$e_{2}$, and $\varphi_{s,t,u,v}(p_{3})$ is on $M(e_{2})$}\\}\\\\[4.30554pt]
R_{\rho}(e_{2})\ =&\\{\varphi_{s,t,u,v}(p_{1}):&\mbox{$(s,t,u,v)\in{\cal
P}(e_{2})$ and $s^{2}+t^{2}\geq\rho^{2}$}\\}.\end{array}$

Observe that ${\cal P}(e_{2})$ is a 2-dimensional convex polygon in
$\mathbb{R}^{4}$ with $O(1)$ edges (since $\varphi_{s,t,u,v}(p_{2})$ and
$\varphi_{s,t,u,v}(p_{3})$ are linear in the variables $s,t,u,v$, and the 2
point-on-line-segment conditions yield 2 linear equality constraints and 4
linear inequality constraints in these 4 variables). Furthermore,
$R_{\rho}(e_{2})$ is a region in $\mathbb{R}^{2}$ which is the intersection of
a convex $O(1)$-gon with the exterior of an ellipse (since
$(s,t,u,v)\mapsto\varphi_{s,t,u,v}(p_{1})$ is a linear projection from
$\mathbb{R}^{4}$ to $\mathbb{R}^{2}$, and the projection of a 2-dimensional
slice of the cylinder $\\{(s,t,u,v):s^{2}+t^{2}=\rho^{2}\\}$ gives an
ellipse).

The decision problem (deciding whether the maximum scaling factor is at least
a given value $\rho$) reduces to finding a pair of vertex $v_{1}$ of
$\Gamma_{1}$ and sub-edge $e_{2}$ of $\Gamma_{2}$, such that $v_{1}\in
R_{\rho}(e_{2})$. To this end, we will build a data structure to store the
$O(n)$ regions $R_{\rho}(e_{2})$ over all $e_{2}$ so that we can quickly
decide whether the query point $v_{1}$ stabs (i.e., is contained in) some
region $R_{\rho}(e_{2})$.

We use standard techniques in geometric data structures. First, we consider
the _range stabbing_ problem for exteriors of ellipses: build a data structure
for a set of $O(n)$ ellipses in $\mathbb{R}^{2}$, so that we can quickly
decide whether a query point stabs the exterior of some ellipse, i.e., whether
a query point is outside the intersection of the interiors of the ellipses.
The intersection of the interiors of $O(n)$ ellipses (which is a single cell
in the arrangement) has almost linear combinatorial complexity by standard
results on Davenport-Schinzel sequences [4], and can be constructed in
$\widetilde{O}(n)$ time, e.g., by divide-and-conquer. Thus, this problem can
be solved with $\widetilde{O}(n)$ preprocessing time and $\widetilde{O}(1)$
query time.

Next, we consider range stabbing for our regions $R_{\rho}(e_{2})$. As each
region is the intersection of a convex $O(1)$-gon with the exterior of an
ellipse, we can use standard _multi-level_ data structuring techniques444
Multi-level data structures are for solving range-searching-related problems,
where in a query, we seek an object satisfying a conjunction of multiple
($O(1)$) constraints. The idea is to take a tree structure for solving the
problem with one constraint, and have each node of the tree recursively store
structures for solving the problem with the remaining constraints. See a
general survey on range searching [3] for more details.  to handle the extra
$O(1)$ halfplane constraints. Generally, halfplane range searching cannot be
solved with near-linear preprocessing time and polylogarithmic query time. But
in our application, all query points $v_{1}$ lie on a convex chain
$\Gamma_{1}$. The constraint that such a query point $v_{1}$ lies inside a
halfplane is equivalent to the condition that $v_{1}$ lies inside one of
$O(1)$ 1D intervals, assuming that the vertices of $\Gamma_{1}$ are stored in
a sorted array. We can therefore use 1D range trees [3, 21, 28] to handle the
halfplane constraints, with only a logarithmic factor increase in the
preprocessing and query time.

The optimization problem reduces to the decision problem by a standard
application of parametric search [23]. (The application requires a
parallelization of the decision algorithm: the preprocessing part, namely, the
construction of the intersection of interiors of ellipses, is
straightforwardly parallelizable by divide-and-conquer; the $O(n)$ queries can
trivially be answered in parallel.) Parametric search increases the running
time by a polylogarithmic factor. Alternatively, we can apply Chan’s
randomized optimization technique [10], which avoids extra factors. (The
application here is straightforward, since the problem can be viewed as a
generalized “closest-pair-type” problem [10] between two sets of objects.) ∎

###  2.3 Simple Divide-and-Conquer Algorithm for $k=3$

We now have all the ingredients needed to put together a simple recursive
algorithm to solve the $k=3$ problem in the 3-contact case:

######  Theorem 4.

Given a triangle $P$ and a convex $n$-gon $Q$, in $\widetilde{O}(n)$ time, we
can find the largest similar copy of $P$ contained in $Q$ that has $1$ vertex
of $P$ at a vertex of $Q$ and the $2$ other vertices of $P$ on edges of $Q$.

###### Proof.

Let $P=\triangle p_{1}p_{2}p_{3}$. Arbitrarily divide $\partial Q$ into $O(1)$
arcs, and let $\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be 3 such arcs (allowing
duplicates). We will try all $O(1)$ choices of
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$.

Let $S$ be an interval. Let $\Gamma_{1}(S)$ (resp. $\Gamma_{2}(S)$ and
$\Gamma_{3}(S)$) be the sub-arc of $\Gamma_{1}$ (resp. $\Gamma_{2}$ and
$\Gamma_{3}$) consisting of all edges whose supporting lines have angles in
$S-\theta_{p_{2}p_{3}}$ (resp. $S-\theta_{p_{1}p_{3}}$ and
$S-\theta_{p_{1}p_{2}}$) (mod $\pi$). We will recursively solve the following
problem: find a similarity transformation $\varphi$, maximizing the scaling
factor, such that $\varphi(p_{1})$ is a vertex $v_{1}$ of $\Gamma_{1}(S)$,
$\varphi(p_{2})$ is on $\Gamma_{2}(S)$, and $\varphi(p_{3})$ is on
$\Gamma_{3}(S)$.

As a first step, we remove edges not participating in
$\Gamma_{1}(S),\Gamma_{2}(S),\Gamma_{3}(S)$, so that the number of edges in
$Q$ is reduced to $m(S):=|\Gamma_{1}(S)|+|\Gamma_{2}(S)|+|\Gamma_{3}(S)|$.
Partition $S$ into sub-intervals $S^{-}$ and $S^{+}$ (as shown in Figure 4) so
that $m(S^{-}),m(S^{+})=m(S)/2\pm O(1)$. We try various possibilities and take
the best solution found:

  * •

Case 1: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{-})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{-})$, and $\varphi(p_{3})$ is on $\Gamma_{3}(S^{-})$. We can
recursively solve the problem for $S^{-}$.

  * •

Case 2: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{+})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{+})$, and $\varphi(p_{3})$ is on $\Gamma_{3}(S^{+})$. We can
recursively solve the problem for $S^{+}$.

  * •

Case 3: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{-})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{+})$, and $\varphi(p_{3})$ is on $\Gamma_{3}(S^{+})$. Since
$\Lambda(\Gamma_{1}(S^{-}))+\theta_{p_{2}p_{3}}\subseteq S^{-}$ and
$\Lambda(\Gamma_{2}(S^{+}))+\theta_{p_{1}p_{3}}\subseteq S^{+}$ are disjoint
(mod $\pi$), and $\Lambda(\Gamma_{1}(S^{-}))+\theta_{p_{2}p_{3}}\subseteq
S^{-}$ and $\Lambda(\Gamma_{3}(S^{+}))+\theta_{p_{1}p_{2}}\subseteq S^{+}$ are
disjoint (mod $\pi$), we can solve this sub-problem by Lemmas 2–3 in
$\widetilde{O}(m(S))$ time.

  * •

Case 4: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{-})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{-})$, and $\varphi(p_{3})$ is on $\Gamma_{3}(S^{+})$. Since
$\Lambda(\Gamma_{2}(S^{-}))+\theta_{p_{1}p_{3}}\subseteq S^{-}$ and
$\Lambda(\Gamma_{3}(S^{+}))+\theta_{p_{1}p_{2}}\subseteq S^{+}$ are disjoint
(mod $\pi$), we can solve this sub-problem by Lemma 1 in $\widetilde{O}(m(S))$
time. Namely, for each vertex $v_{1}$ of $\Gamma_{1}(S^{-})$, we just check
the unique similarity transformation $\varphi$ with $\varphi(p_{1})=v_{1}$ and
$\varphi(p_{2})=X(v_{1})$.

All remaining cases are symmetric to Cases 3 and 4 (swapping subscripts 2 and
3 and/or $S^{-}$ and $S^{+}$).

Letting $m=m(S)$, we obtain the following recurrence for the running time:

$T(m)\>\leq\>2\,T(m/2+O(1))+\widetilde{O}(m).$

The recurrence solves to $T(m)=\widetilde{O}(m)$. ∎

It is not difficult to modify the algorithm to also solve the 2-contact
(2-anchor) case, as shown in Appendix A. This gives a complete
$\widetilde{O}(n)$ time algorithm for $k=3$.

Figure 4: Partitioning each $\Gamma_{i}(S)$ into $\Gamma_{i}(S^{+})$ and
$\Gamma_{i}(S^{-})$, for $i\in\\{1,2,3\\}$.

###  2.4 Generalizing to $k>3$

With further effort, we can also solve the problem for general $k$ in the
3-contact case. Say $p_{1}$ is the anchor vertex, and $p_{2}$ and $p_{3}$ are
the other two vertices of $P$ in contact with $Q$. The idea is to just apply
the Pairing Lemma to the triangles $\triangle p_{1}p_{2}p_{i}$ for all other
vertices $p_{i}$ of $P$, assuming appropriate disjointness conditions. We need
to extend the problem to equip each vertex $v_{1}$ of $\Gamma_{1}$ with a sub-
arc $I(v_{1})$ of $\Gamma_{2}$ which restricts the placement of $p_{2}$. The
resulting range searching sub-problems can be solved in a manner similar to
the triangle case, which we show in the following extension of Lemma 3:

######  Lemma 5.

Let $P$ be a $k$-gon with vertices $p_{1},\ldots,p_{k}$ (not necessarily in
sorted order). Let $\Gamma_{1},\ldots,\Gamma_{k}$ be arcs of a convex $n$-gon
$Q$, such that

  1. 1.

for each $i\in\\{3,\ldots,k\\}$, $\Lambda(\Gamma_{1})+\theta_{p_{2}p_{i}}$ and
$\Lambda(\Gamma_{2})+\theta_{p_{1}p_{i}}$ are disjoint (mod $\pi$), and

  2. 2.

for each $i\in\\{3,\ldots,k\\}$, $\Lambda(\Gamma_{1})+\theta_{p_{2}p_{i}}$ and
$\Lambda(\Gamma_{i})+\theta_{p_{1}p_{2}}$ are disjoint (mod $\pi$).

For each vertex $v_{1}$ of $\Gamma_{1}$, we are given a sub-arc $I(v_{1})$ of
$\Gamma_{2}$. In $\widetilde{O}(k^{2}n)$ time, we can find a similarity
transformation $\varphi$, maximizing the scaling factor, such that
$\varphi(p_{1})$ is a vertex $v_{1}$ of $\Gamma_{1}$, $\varphi(p_{2})$ is on
$I(v_{1})\subseteq\Gamma_{2}$, $\varphi(p_{3})$ is on $\Gamma_{3}$, and for
each $i\in\\{4,\ldots,k\\}$, $\varphi(p_{i})$ is left of
$\overleftrightarrow{\Gamma_{i}}$.

###### Proof.

We generalize the proof of Lemma 3. For each $i\in\\{3,\ldots,k\\}$, we apply
Lemma 1 to $\triangle p_{1}p_{2}p_{i},\Gamma_{1},\Gamma_{2},\Gamma_{i}$, to
obtain a pairing $M_{i}$ between $\Gamma_{2}$ and $\Gamma_{i}$. We then
overlay the $O(k)$ subdivisions of $\Gamma_{2}$. In doing so, the mapping
$M_{i}$ from sub-edges of $\Gamma_{2}$ to sub-edges of $\Gamma_{i}$ may not be
bijective, but this is fine. The number of sub-edges is $n^{\prime}=O(kn)$. We
further subdivide $\Gamma_{2}$ at the endpoints of the sub-arcs $I(v_{1})$ for
every vertex $v_{1}$ of $\Gamma_{1}$. As a consequence, the following property
holds:

> For every similarity transformation $\varphi$ that has $\varphi(p_{1})$
> being a vertex $v_{1}$ of $\Gamma_{1}$ and $\varphi(p_{2})$ on a sub-edge
> $e_{2}$ of $\Gamma_{2}$, we have: (i) $\varphi(p_{3})$ is on $\Gamma_{3}$
> iff $\varphi(p_{3})$ is on $M_{3}(e_{2})$, and (ii) for each
> $i\in\\{4,\ldots,k\\}$, $\varphi(p_{i})$ is left of
> $\overleftrightarrow{\Gamma_{i}}$ iff $\varphi(p_{i})$ is left of
> $\overleftrightarrow{M_{i}(e_{2})}$.

For each sub-edge $e_{2}$ of $\Gamma_{2}$, define

$\begin{array}[]{rrl}{\cal P}(e_{2})\
=&\\{(s,t,u,v)\in\mathbb{R}^{4}:&\mbox{$\varphi_{s,t,u,v}(p_{2})$ is on
$e_{2}$, and $\varphi_{s,t,u,v}(p_{3})$ is on $M_{3}(e_{2})$,
and}\\\\[2.15277pt] &&\mbox{$\varphi_{s,t,u,v}(p_{i})$ is left of
$\overleftrightarrow{M_{i}(e_{2})}$ for all
$i\in\\{4,\ldots,k\\}$}\\}\\\\[4.30554pt] R_{\rho}(e_{2})\
=&\\{\varphi_{s,t,u,v}(p_{1}):&\mbox{$(s,t,u,v)\in{\cal P}(e_{2})$ and
$s^{2}+t^{2}\geq\rho^{2}$}\\}.\end{array}$

Similar to before, ${\cal P}(e_{2})$ is a 2-dimensional polygon in
$\mathbb{R}^{4}$, with $O(k)$ edges, and $R_{\rho}(e_{2})$ is a region in
$\mathbb{R}^{2}$ which is the intersection of a convex $O(k)$-gon with the
exterior of an ellipse.

The decision problem reduces to finding a pair of vertex $v_{1}$ of
$\Gamma_{1}$ and sub-edge $e_{2}$ of $\Gamma_{2}$, such that $v_{1}\in
R_{\rho}(e_{2})$ and $e_{2}$ is in $I(v_{1})$. To this end, we will build a
data structure to store the $O(n^{\prime})$ regions $R_{\rho}(e_{2})$ over all
$e_{2}$ so that, given a query point $v_{1}$ and a query sub-arc $I$, we can
quickly decide whether the query point $v_{1}$ stabs some region
$R_{\rho}(e_{2})$ with $e_{2}$ in the query sub-arc $I$.

Each such region can be decomposed into $O(k)$ sub-regions, where each sub-
region is the intersection of the exterior of an ellipse with $O(1)$
halfplanes (the preprocessing time is increased by an $O(k)$ factor). As
before, we can use ellipse range stabbing combined with multi-level data
structuring techniques (1D range tree). The constraint that $e_{2}$ is in the
query sub-arc $I$ (which can be represented as a 1D interval) can again be
handled by multi-leveling, with another level of 1D range trees. The
preprocessing time is $\widetilde{O}(kn^{\prime})$ and the query time is
$\widetilde{O}(1)$. The optimization problem reduces to the decision problem
by standard parametric search (or randomized search) as before. ∎

We now give a slightly more intricate divide-and-conquer algorithm for general
$k$:

######  Theorem 6.

Given a $k$-gon $P$ and a convex $n$-gon $Q$ (where $k\leq n$), we can find
the largest similar copy of $P$ contained in $Q$ that has $1$ vertex of $P$ at
a vertex of $Q$ and the $2$ other vertices of $P$ on $2$ edges of $Q$, in
$O(k^{O(1/\varepsilon)}n^{1+\varepsilon})$ time for any $\varepsilon>0$.

###### Proof.

Suppose the vertices of $P$ are $p_{1},\ldots,p_{k}$ (not necessarily in
sorted order). Divide $\partial Q$ into $O(1)$ arcs, and let
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be 3 such arcs (allowing duplicates). We
will try all choices for $p_{1},p_{2},p_{3}$ and
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$; this increases the final running time by a
factor of $O(k^{3})$.

Let $\Gamma_{4},\ldots,\Gamma_{k}$ be arcs of $\partial Q$, so that a
similarity transformation $\varphi$ has $\varphi(P)$ inside $Q$ iff
$\varphi(p_{i})$ is left of $\overleftrightarrow{\Gamma_{i}}$ for all
$i\in\\{1,\dots k\\}$. This is w.l.o.g. since we can just make $O(1)$ copies
of $p_{4},\ldots,p_{k}$ and associate each copy with an arc of $\partial Q$,
while increasing $k$ by a constant factor. Note that duplicate arcs are
allowed, and some of these arcs may even be the same as $\Gamma_{1}$,
$\Gamma_{2}$, or $\Gamma_{3}$.

We will describe a recursive algorithm, where the input consists of $k$ arcs
$\langle\Gamma_{1},\ldots,\Gamma_{k}\rangle$ together with a sub-arc
$I(v_{1})\subseteq\Gamma_{2}$ for every vertex $v_{1}$ of $\Gamma_{1}$. (For
the initial problem, $I(v_{1})$ will be all of $\Gamma_{2}$ for all $v_{1}$.)
Our algorithm will find a similarity transformation $\varphi$, maximizing the
scaling factor, such that $\varphi(p_{1})$ is a vertex $v_{1}$ of
$\Gamma_{1}$, $\varphi(p_{2})$ is on $I(v_{1})$, $\varphi(p_{3})$ is on
$\Gamma_{3}$, and for all $i\in\\{4,\ldots,k\\}$, $\varphi(p_{i})$ is left of
$\overleftrightarrow{\Gamma_{i}}$.

To this end, let $\textrm{clip}_{i}(\Gamma_{i},\Gamma_{2})$ be the sub-arc of
$\Gamma_{i}$ consisting of all edges of $\Gamma_{i}$ whose supporting lines
have angles in $\Lambda(\Gamma_{2})+\theta_{p_{1}p_{i}}-\theta_{p_{1}p_{2}}$
(mod $\pi$). Let
$m(\Gamma_{2})=\sum_{i=3}^{k}|\textrm{clip}_{i}(\Gamma_{i},\Gamma_{2})|+|\Gamma_{2}|$.
Partition $\Gamma_{1}$ into $r$ sub-arcs such that each sub-arc $\gamma_{1}$
has $|\Gamma_{1}|/r\pm O(1)$ edges. Partition $\Gamma_{2}$ into $r$ sub-arcs
such that each sub-arc $\gamma_{2}$ has $m(\gamma_{2})=m(\Gamma_{2})/r\pm
O(k)$. (This is possible because for a single edge $e_{2}$ of $\gamma_{2}$,
$m(e_{2})\leq O(k)$.)

By Lemma 1, we first enumerate all similarity transformations $\varphi$ with
$\varphi(p_{1})$ on a vertex of $\Gamma_{1}$, $\varphi(p_{2})$ on some sub-arc
$\gamma_{2}$, and $\varphi(p_{3})$ on each of the $O(1)$ contiguous pieces of
$\Gamma_{3}\setminus\textrm{clip}_{3}(\Gamma_{3},\gamma_{2})$; the
disjointness condition in Lemma 1 is satisfied by our definition of
$\textrm{clip}_{i}$ (see Figure 5). This gives $O(|\Gamma_{1}|)$
transformations to check per $\gamma_{2}$, which requires
$\widetilde{O}(|\Gamma_{1}|\cdot rk)$ time over all $\gamma_{2}$ (checking the
feasibility of one transformation takes $O(k\log n)$ time, since we can tell
whether any given point is inside $Q$ via binary search [28]).

Figure 5: Example where both sub-arcs constituting
$\Gamma_{3}\setminus\textrm{clip}_{3}(\Gamma_{3},\gamma_{2})$ (denoted
$(\Gamma_{3}\setminus\textrm{clip}_{3}(\Gamma_{3},\gamma_{2}))^{+}$ and
$(\Gamma_{3}\setminus\textrm{clip}_{3}(\Gamma_{3},\gamma_{2}))^{-}$) have a
similarity transformation that places $p_{1}$ at a vertex $v_{1}$ of
$\Gamma_{1}$, $p_{2}$ on $\gamma_{2}$, and $p_{3}$ on
$\Gamma_{3}\setminus\textrm{clip}_{3}(\Gamma_{3},\gamma_{2})$. $X^{+}(v_{1})$
and $X^{-}(v_{2})$ can be found rapidly via Lemma 1 since
$(\Lambda(\Gamma_{3}\setminus\textrm{clip}_{3}(\Gamma_{3},\gamma_{2}))+\theta_{p_{1}p_{2}})\cap(\Lambda(\gamma_{2})+\theta_{p_{1}p_{3}})=\emptyset$
(mod $\pi)$. Dashed triangles are similar to $\triangle p_{1}p_{2}p_{3}$.

It remains to search for transformations $\varphi$ such that $\varphi(p_{1})$
is on a vertex of some sub-arc $\gamma_{1}$, $\varphi(p_{2})$ is on some sub-
arc $\gamma_{2}$, and $\varphi(p_{3})$ is on
$\textrm{clip}_{3}(\Gamma_{3},\gamma_{2})$. There are two possibilities:

  * •

Case 1: For each $i\in\\{3,\ldots,k\\}$,
$\Lambda(\gamma_{1})+\theta_{p_{2}p_{i}}$ and
$\Lambda(\gamma_{2})+\theta_{p_{1}p_{i}}$ are disjoint (mod $\pi$). For each
$i\in\\{3,\ldots,k\\}$, we apply Lemma 1 to
$(\gamma_{1},\gamma_{2},\gamma^{\prime})$ for each of the $O(1)$ contiguous
pieces $\gamma^{\prime}$ of
$\Gamma_{i}\setminus\textrm{clip}_{i}(\Gamma_{i},\gamma_{2})$. For each vertex
$v_{1}$ of $\gamma_{1}$, let $I^{\prime}(v_{1})$ be the intersection of all
sub-arcs $I(v_{1})$ produced during these applications of Lemma 1. We now use
Lemma 5 on
$\langle\gamma_{1},\gamma_{2},\textrm{clip}_{3}(\Gamma_{3},\gamma_{2}),\ldots,\textrm{clip}_{k}(\Gamma_{k},\gamma_{2})\rangle$.
The sub-arc we pass to Lemma 5 for each vertex $v_{1}$ of $\gamma_{1}$ is
$I(v_{1})\cap I^{\prime}(v_{1})$. The total time for all instances of this
case is $\widetilde{O}(r^{2}\cdot k^{2}(|\Gamma_{1}|/r+m(\Gamma_{2})/r+k))$
(since we can operate on a truncated version of $Q$ consisting of just the
arcs/sub-arcs specified).

  * •

Case 2: For some $i\in\\{3,\ldots,k\\}$,
$\Lambda(\gamma_{1})+\theta_{p_{2}p_{i}}$ and
$\Lambda(\gamma_{2})+\theta_{p_{1}p_{i}}$ intersect (mod $\pi$). Here, we
recursively solve the problem for
$\langle\gamma_{1},\gamma_{2},\textrm{clip}_{3}(\Gamma_{3},\gamma_{2}),\ldots,\textrm{clip}_{k}(\Gamma_{k},\gamma_{2})\rangle$.
The sub-arc we pass to the recursive call for each vertex $v_{1}$ of
$\gamma_{1}$ is $I(v_{1})\cap I^{\prime}(v_{1})$, where $I^{\prime}(v_{1})$ is
defined as in Case 1. There are $O(r)$ pairs $(\gamma_{1},\gamma_{2})$
satisfying this condition per $i$, since when we overlay two subdivisions of
$\mathbb{R}$ into $O(r)$ intervals, the number of intersecting pairs of
intervals is $O(r)$. Thus, the total number of recursive calls for this case
is $O(kr)$. The time to produce the sub-problems is subsumed by the time bound
in Case 1.

We take the best solution found in all cases. Letting
$\widehat{m}=|\Gamma_{1}|+m(\Gamma_{2})$, we obtain the following recurrence
for the running time:

$T(\widehat{m})\>\leq\>O(kr)\,T(\widehat{m}/r+O(k))+\widetilde{O}(k^{2}r^{2}(\widehat{m}/r+k)).$

As base case, if $\widehat{m}\leq kr$, we use the naive bound
$T(\widehat{m})=O(k^{2}\widehat{m}^{2})$ by constructing the space of all
feasible placements [1]. The recurrence solves to $T(\widehat{m})\leq
O(k)^{\log_{r}\widehat{m}}\cdot(kr)^{O(1)}\widehat{m}$. Choosing
$r=\widehat{m}^{\varepsilon}$ yields $T(\widehat{m})\leq
k^{O(1/\varepsilon)}\widehat{m}^{1+O(\varepsilon)}$. (We can adjust
$\varepsilon$ by a constant factor.) ∎

Note that our earlier divide-and-conquer approach in Theorem 4 (which yielded
a slightly better
$O(n\mathop{\rm polylog}n)$ running time) does not work here. This is because
we need to ensure disjointness conditions for multiple triangles $\triangle
p_{1}p_{2}p_{i}$ with different rotational shifts, meaning that we cannot use
one common interval $S$ to represent the $k$ arcs in a sub-problem.

It is not difficult to modify the algorithm to solve the 2-contact (2-anchor)
case, as shown in Appendix A.

Extension to the 4-contact case is more challenging, however. Without an
anchor vertex, Lemma 1 is no longer applicable, so we cannot clip arcs as in
Theorem 6’s proof. With some care, we could still use the Pairing Lemma to
solve the problem, but we would need to pair some arcs $\Gamma_{i}$ with
$\Gamma_{2}$ and some arcs $\Gamma_{i}$ with another arc such as $\Gamma_{1}$.
As a result, the range searching sub-problems become more complex, and the
running time would be much larger (though subquadratic). In the next section,
we suggest a better, more elegant way to solve the 4-contact case in near-
linear time, without needing range searching at all!

##  3 4-Contact (No-Anchor) Case

To solve the 4-contact case, we will actually show that the number of
solutions (not necessarily optimal nor locally optimal) is actually near-
linear in $n$, assuming general position input.555 In degenerate scenarios,
e.g., when $P$ and $Q$ are squares, there could technically be an infinite
number of 4-contact placements; in such cases, we may apply small
perturbations, or instead count the number of distinct quadruples of edges of
$Q$ corresponding to such placements.  This allows us to focus on the problem
of enumerating all 4-contact placements (as we can check their feasibility
rapidly). For the enumeration problem, we can immediately reduce the general
$k$ case to the $k=4$ case.

###  3.1 Covering All 3-Contact Solutions by Pairs and Triples for $k=3$

To solve the enumeration problem for $k=4$, we will actually revisit the $k=3$
case. Although the number of 3-contact solutions may be quadratic in the worst
case, we observe that our divide-and-conquer algorithm from Theorem 4 can
generate a near-linear number of pairs that “cover” all 3-contact solutions.
To be precise, we make the following definitions: We say that
$(q_{1},q_{2},q_{3})$ is _covered_ by a list $L$ of triples of edges if
$q_{1}$ is on $e_{1}$, $q_{2}$ is on $e_{2}$, and $q_{3}$ is on $e_{3}$ for
some $(e_{1},e_{2},e_{3})\in L$. We say that $(q_{1},q_{2})$ is _covered_ by a
pairing $M$ of sub-edges if $q_{1}$ is on $e_{1}$ and $q_{2}$ is on $M(e_{1})$
for some sub-edge $e_{1}$.

We begin with a variant of the Pairing Lemma that guarantees monotonically
_increasing_ pairings, which will be crucial later:

######  Lemma 7.

_(Modified Pairing Lemma)_ Let $\triangle p_{1}p_{2}p_{3}$ be a triangle. Let
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be arcs of a convex $n$-gon $Q$, such that

  1. 1.

$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}$ and
$\Lambda(\Gamma_{2})+\theta_{p_{1}p_{3}}$ are disjoint (mod $\pi$), and

  2. 2.

$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}$ and
$\Lambda(\Gamma_{3})+\theta_{p_{1}p_{2}}$ are disjoint (mod $\pi$).

In $\widetilde{O}(n)$ time, we can compute a monotonically _increasing_
pairing $M$ between $\Gamma_{2}$ and $\Gamma_{3}$ with $O(n)$ sub-edges, or a
list $L$ of $O(n)$ triples of edges, satisfying the following property:

> For every similarity transformation $\varphi$ that has $\varphi(p_{1})$ on
> $\Gamma_{1}$ and $\varphi(p_{2})$ on $\Gamma_{2}$ and $\varphi(p_{3})$ on
> $\Gamma_{3}$, we have $(\varphi(p_{2}),\varphi(p_{3}))$ covered by $M$ or
> $(\varphi(p_{1}),\varphi(p_{2}),\varphi(p_{3}))$ covered by $L$.

Before proving Lemma 7, we first analyze an easy special case:

######  Lemma 8.

Let $\triangle p_{1}p_{2}p_{3}$ be a triangle. Let
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be arcs of a convex $n$-gon $Q$, such that

  1. 1.

$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}$ and
$\Lambda(\Gamma_{2})+\theta_{p_{1}p_{3}}$ are disjoint (mod $\pi$),

  2. 2.

$\Lambda(\Gamma_{1})+\theta_{p_{2}p_{3}}$ and
$\Lambda(\Gamma_{3})+\theta_{p_{1}p_{2}}$ are disjoint (mod $\pi$),

  3. 3.

$\Lambda(\Gamma_{2})+\theta_{p_{1}p_{3}}$ and
$\Lambda(\Gamma_{3})+\theta_{p_{1}p_{2}}$ are disjoint (mod $\pi$).

In $\widetilde{O}(n)$ time, we can compute a list $L$ of $O(n)$ triples of
edges, satisfying the following property:

> For every similarity transformation $\varphi$ that has $\varphi(p_{1})$ on
> $\Gamma_{1}$, $\varphi(p_{2})$ on $\Gamma_{2}$, and $\varphi(p_{3})$ on
> $\Gamma_{3}$, we have $(\varphi(p_{1}),\varphi(p_{2}),\varphi(p_{3}))$
> covered by $L$.

###### Proof.

We apply Lemma 2 twice, to obtain a pairing $M_{12}$ between $\Gamma_{1}$ and
$\Gamma_{2}$ and a pairing $M_{23}$ between $\Gamma_{2}$ and $\Gamma_{3}$. We
overlay the 2 subdivisions along $\Gamma_{2}$. We can then append the triples
$(M_{12}(e_{2}),e_{2},M_{23}(e_{2}))$ over all sub-edges $e_{2}$ of
$\Gamma_{2}$ to $L$. ∎

To prove Lemma 7, we show that any monotonically decreasing pairing actually
implies a division of the arcs into sub-problems that can be processed using
Lemma 8:

###### Proof.

We apply Lemma 2 to obtain a pairing $M$, which already satisfies the lemma if
$M$ is monotonically increasing. We now describe how to convert $M$ to a list
$L$ of triples if it is monotonically decreasing.

Let $\Gamma_{2}^{-}(t)$ (resp. $\Gamma_{2}^{+}(t)$) be the sub-arc of
$\Gamma_{2}$ consisting of all edges whose supporting lines’ angles are in the
interval $(t-\theta_{p_{1}p_{3}}-\pi/2$, $t-\theta_{p_{1}p_{3}}]$ (mod $\pi$)
(resp. $[t-\theta_{p_{1}p_{3}},t-\theta_{p_{1}p_{3}}+\pi/2]$ (mod $\pi$)).
$\Gamma_{2}^{-}(t)$ and $\Gamma_{2}^{+}(t)$ may share at most one edge. The
intervals allow wrap-around, so $(a,b]$ indicates $(a,\pi)\cup[0,b]$ if $a>b$.
Let $\Gamma_{3}^{-}(t)$ and $\Gamma_{3}^{+}(t)$ be defined similarly. Let
$q_{2}(t)$ denote the dividing point (or shared edge) between
$\Gamma_{2}^{-}(t)$ and $\Gamma_{2}^{+}(t)$, and let $q_{3}(t)$ denote the
dividing point (or shared edge) between $\Gamma_{3}^{-}(t)$ and
$\Gamma_{3}^{+}(t)$. As $t$ increases, both $q_{2}(t)$ and $q_{3}(t)$ are
monotonically increasing, i.e., move in ccw order. Since $M$ is monotonically
decreasing, we can find (via binary search) a value of $t$ such that a sub-
edge incident to (or contained within) $q_{2}(t)$ is paired with a sub-edge
incident to (or contained within) $q_{3}(t)$. Let us fix this value of $t$.

As long as at least one of $q_{2}(t)$ or $q_{3}(t)$ is not an edge, we have
that $\Lambda(\Gamma_{2}^{-}(t))+\theta_{p_{1}p_{3}}$ and
$\Lambda(\Gamma_{3}^{+}(t))+\theta_{p_{1}p_{2}}$ are disjoint (mod $\pi$). In
this case, we can apply Lemma 8 to
$(\Gamma_{1},\Gamma_{2}^{-}(t),\Gamma_{3}^{+}(t))$ to get $O(n)$ triples.
Similarly, we can apply Lemma 8 to
$(\Gamma_{1},\Gamma_{2}^{+}(t),\Gamma_{3}^{-}(t))$ to get $O(n)$ triples. On
the other hand, in $M$, there are no pairs of sub-edges in $\Gamma_{2}^{-}(t)$
with sub-edges in $\Gamma_{3}^{-}(t)$, nor pairs of sub-edge in
$\Gamma_{2}^{+}(t)$ with sub-edges in $\Gamma_{3}^{+}(t)$.

If $q_{2}(t)$ and $q_{3}(t)$ are both edges, then there exists exactly one
sub-edge $e_{2}$ of $q_{2}(t)$ paired with a sub-edge $e_{3}$ of $q_{3}(t)$.
We enumerate all $O(n)$ triples of the form $(e_{1},q_{2}(t),q_{3}(t))$ and
append these to $L$. Then, we apply Lemma 8 to
$(\Gamma_{1},\Gamma_{2}^{-}(t)\setminus e_{2},\Gamma_{3}^{+}(t)\setminus
e_{3})$ and $(\Gamma_{1},\Gamma_{2}^{+}(t)\setminus
e_{2},\Gamma_{3}^{-}(t)\setminus e_{3})$ as before. Note that one or more of
$\Gamma_{2}^{-}(t)\setminus e_{2}$, $\Gamma_{2}^{+}(t)\setminus e_{2}$,
$\Gamma_{3}^{-}(t)\setminus e_{3}$, or $\Gamma_{3}^{+}(t)\setminus e_{3}$
might consist of two contiguous pieces instead of one; this can be handled by
applying Lemma 8 to all $O(1)$ combinations of contiguous pieces. ∎

By adapting our $k=3$ algorithm, we can cover all 3-contact solutions by
$O(\log n)$ monotonically increasing pairings, together with an extra set of
$O(n\log n)$ triples:

######  Theorem 9.

Let $\triangle p_{1}p_{2}p_{3}$ be a triangle. Let
$\Gamma_{1},\Gamma_{2},\Gamma_{3}$ be arcs of a convex $n$-gon $Q$. In
$\widetilde{O}(n)$ time, we can compute a collection ${\cal M}$ of $O(\log n)$
monotonically _increasing_ pairings between $\Gamma_{1}$ and $\Gamma_{2}$,
between $\Gamma_{2}$ and $\Gamma_{3}$, and between $\Gamma_{1}$ and
$\Gamma_{3}$, each with $O(n)$ sub-edges, and a list $L$ of $O(n\log n)$
triples of edges, satisfying the following property:

> For every similarity transformation $\varphi$ that has $\varphi(p_{1})$ on
> $\Gamma_{1}$ and $\varphi(p_{2})$ on $\Gamma_{2}$ and $\varphi(p_{3})$ on
> $\Gamma_{3}$, we have $(\varphi(p_{1}),\varphi(p_{2}))$ or
> $(\varphi(p_{2}),\varphi(p_{3}))$ or $(\varphi(p_{1}),\varphi(p_{3}))$
> covered by some pairing in ${\cal M}$, or
> $(\varphi(p_{1}),\varphi(p_{2}),\varphi(p_{3}))$ covered by $L$.

###### Proof.

We modify the divide-and-conquer algorithm in the proof of Theorem 4. Let $S$
be an interval. Define $\Gamma_{1}(S),\Gamma_{2}(S),\Gamma_{3}(S)$ as before.
We will recursively solve the problem for
$\Gamma_{1}(S),\Gamma_{2}(S),\Gamma_{3}(S)$.

As a first step, we remove edges not participating in
$\Gamma_{1}(S),\Gamma_{2}(S),\Gamma_{3}(S)$, so that the number of edges in
$Q$ reduced to $m(S):=|\Gamma_{1}(S)|+|\Gamma_{2}(S)|+|\Gamma_{3}(S)|$. Divide
$S$ into two disjoint sub-intervals $S^{-}$ and $S^{+}$ so that
$m(S^{-}),m(S^{+})=m(S)/2\pm O(1)$. We consider various possibilities:

  * •

Case 1: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{-})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{-})$, and $\varphi(p_{3})$ is on $\Gamma_{3}(S^{-})$. We can
recursively solve the problem for $S^{-}$.

  * •

Case 2: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{+})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{+})$, and $\varphi(p_{3})$ is on $\Gamma_{3}(S^{+})$. We can
recursively solve the problem for $S^{+}$.

  * •

Case 3: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{-})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{+})$, and $\varphi(p_{3})$ is on $\Gamma_{3}(S^{+})$. Since
$\Lambda(\Gamma_{1}(S^{-}))+\theta_{p_{2}p_{3}}\subseteq S^{-}$ and
$\Lambda(\Gamma_{2}(S^{+}))+\theta_{p_{1}p_{3}}\subseteq S^{+}$ are disjoint,
and $\Lambda(\Gamma_{1}(S^{-}))+\theta_{p_{2}p_{3}}\subseteq S^{-}$ and
$\Lambda(\Gamma_{3}(S^{+}))+\theta_{p_{1}p_{2}}\subseteq S^{+}$ are disjoint
(mod $\pi$), we can solve the problem by Lemma 7 in $\widetilde{O}(m(S))$
time.

All remaining cases are symmetric to Case 3. (The previous Case 4 is now
symmetric to Case 3, since $p_{1}$ is no longer treated as a special anchor
vertex.)

A pairing between $\Gamma_{1}(S^{-})$ and $\Gamma_{2}(S^{-})$ and a pairing
between $\Gamma_{1}(S^{+})$ and $\Gamma_{2}(S^{+})$ produced by the recursive
calls in Cases 1 and 2 can be joined into one pairing while remaining
monotonically increasing, since $\Gamma_{1}(S^{-})$ precedes
$\Gamma_{1}(S^{+})$ and $\Gamma_{2}(S^{-})$ precedes $\Gamma_{2}(S^{+})$ in
ccw order. We can join the pairings for $\Gamma_{2},\Gamma_{3}$ and
$\Gamma_{1},\Gamma_{3}$ similarly. (And we can trivially union the lists of
triples together.)

This yields a total of $O(\log n)$ pairings each with $O(n)$ sub-edges, plus
an extra list of $O(n\log n)$ triples. ∎

###  3.2 Enumerating All 4-Contact Solutions for $k=4$

To solve the enumeration problem for $k=4$, we claim that we do not need any
further ingredients! We can just run our $k=3$ algorithm for each of the 4
triangles from the input 4-gon and then piece the outputs together in a
careful way.

######  Lemma 10.

Let $p_{1}p_{2}p_{3}p_{4}$ be a $4$-gon and $Q$ be a convex $n$-gon in general
position. Given 3 edges $e_{1},e_{2},e_{3}$ of $Q$, there are only $O(1)$
similarity transformations $\varphi$ with $\varphi(p_{1})$ on $e_{1}$,
$\varphi(p_{2})$ on $e_{2}$, $\varphi(p_{3})$ on $e_{3}$, and $\varphi(p_{4})$
on $\partial Q$, and they can be computed in $O(\log n)$ time.

###### Proof.

Let $\varphi_{s,t,u,v}$ be as before. Define

$\mathcal{L}=\\{(s,t,u,v)\in\mathbb{R}^{4}:\mbox{$\varphi_{s,t,u,v}(p_{1})$ is
on $e_{1}$, $\varphi_{s,t,u,v}(p_{2})$ is on $e_{2}$, and
$\varphi_{s,t,u,v}(p_{3})$ is on $e_{3}$}\\}.$

Then $\mathcal{L}$ is a line segment in $\mathbb{R}^{4}$ (since there are 3
linear equality constraints and 6 inequality constraints in the variables
$s,t,u,v$). Thus,
$\mathcal{L}^{\prime}=\\{\varphi_{s,t,u,v}(p_{4}):(s,t,u,v)\in\mathcal{L}\\}$
is a line segment in $\mathbb{R}^{2}$. The edges we want correspond to
intersections of $\mathcal{L}^{\prime}$ with $\partial Q$. There are at most 2
such intersections, and they can be found via binary search [28]. ∎

######  Theorem 11.

Let $P$ be a $4$-gon with vertices $p_{1},p_{2},p_{3},p_{4}$ and $Q$ be a
convex $n$-gon in general position. There are at most $O(n\log^{2}n)$
similarity transformations $\varphi$ such that
$\varphi(p_{1}),\varphi(p_{2}),\varphi(p_{3}),\varphi(p_{4})$ are on $\partial
Q$, and they can be enumerated in $\widetilde{O}(n)$ time.

###### Proof.

Divide $\partial Q$ into $O(1)$ arcs, and let $\Gamma_{1},\ldots,\Gamma_{4}$
be 4 such arcs of $Q$. (We will try all $O(1)$ choices for
$\Gamma_{1},\ldots,\Gamma_{4}$.) We apply Theorem 9 to the 4 triangles
$\triangle p_{1}p_{2}p_{3}$, $\triangle p_{1}p_{2}p_{4}$, $\triangle
p_{1}p_{3}p_{4}$, and $\triangle p_{2}p_{3}p_{4}$, to get a combined
collection ${\cal M}$ of $O(\log n)$ monotonically increasing pairings and a
combined list $L$ of triples.

We consider various possibilities (we will try them all and return the union
of the outputs). If $(\varphi(p_{1}),\varphi(p_{2}),\\\ \varphi(p_{3}))$,
$(\varphi(p_{1}),\varphi(p_{2}),\varphi(p_{4}))$,
$(\varphi(p_{1}),\varphi(p_{3}),\varphi(p_{4}))$, or
$(\varphi(p_{2}),\varphi(p_{3}),\varphi(p_{4}))$ is covered by $L$, we can
examine each of the $O(n\log n)$ triples in $L$, and use Lemma 10 to generate
$O(1)$ transformations $\varphi$ per triple, in $\widetilde{O}(n)$ time.

Otherwise, define a small graph $G_{\varphi}$ with vertices $\\{1,2,3,4\\}$,
where $ij$ is an edge iff $(\varphi(p_{i}),\varphi(p_{j}))$ is covered by a
pairing in ${\cal M}$. We know that each of triple of vertices contains an
edge in $G_{\varphi}$. It is easy to see (from a short case analysis) that
$G_{\varphi}$ must have $\geq 2$ edges.

  * •

Case 1: $G_{\varphi}$ contains 2 adjacent edges, w.l.o.g., 12 and 23. Then
$(\varphi(p_{1}),\varphi(p_{2}))$ is covered by a pairing $M_{12}\in{\cal M}$
between $\Gamma_{1}$ and $\Gamma_{2}$, and $(\varphi(p_{2}),\varphi(p_{3}))$
is covered by a pairing $M_{23}\in{\cal M}$ between $\Gamma_{2}$ and
$\Gamma_{3}$. We overlay the 2 subdivisions along $\Gamma_{2}$. We examine the
triple $(M_{12}(e_{2}),e_{2},M_{23}(e_{2}))$ for each sub-edge $e_{2}$ of
$\Gamma_{2}$, and use Lemma 10 to generate $O(1)$ transformations $\varphi$
per triple, in $\widetilde{O}(n)$ time. The total number of resulting triples
over all $O(\log^{2}n)$ choices of $M_{12}$ and $M_{23}$ is $O(n\log^{2}n)$,
giving $O(n\log^{2}n)$ transformations.

  * •

Case 2: $G_{\varphi}$ contains 2 independent edges, w.l.o.g., 12 and 34. Then
$(\varphi(p_{1}),\varphi(p_{2}))$ is covered by a pairing $M_{12}\in{\cal M}$
between $\Gamma_{1}$ and $\Gamma_{2}$, and $(\varphi(p_{3}),\varphi(p_{4}))$
is covered by a pairing $M_{34}\in{\cal M}$ between $\Gamma_{3}$ and
$\Gamma_{4}$.

For 2 sub-edges $e$ and $e^{\prime}$, define the angle interval
$\Theta(e,e^{\prime})=\\{\theta_{qq^{\prime}}:q\in e,\ q^{\prime}\in
e^{\prime}\\}$. It suffices to enumerate quadruples
$(e_{1},M_{12}(e_{1}),e_{3},M_{34}(e_{3}))$ over all sub-edges $e_{1}$ of
$\Gamma_{1}$ and all sub-edges $e_{3}$ of $\Gamma_{3}$, under the restriction
that $\Theta(e_{1},M_{12}(e_{1}))-\theta_{p_{1}p_{2}}$ intersects
$\Theta(e_{3},M_{34}(e_{3}))-\theta_{p_{3}p_{4}}$ (mod $\pi$). See Figure 6
for an example quadruple.

Observe that because $M_{12}$ is monotonically increasing, the angle intervals
$\Theta(e_{1},M_{12}(e_{1}))$ are disjoint666$\Theta(e_{1},M_{12}(e_{1}))$ and
$\Theta(e_{1}^{\prime},M_{12}(e_{1}^{\prime}))$ may share a limit point if
$e_{1}$ and $e_{1}^{\prime}$ are adjacent, but this does not affect the proof.
and move monotonically as $e_{1}$ moves in ccw order. Similarly, because
$M_{34}$ is monotonically increasing, the angle intervals
$\Theta(e_{3},M_{34}(e_{3}))$ are disjoint and move monotonically as $e_{3}$
moves in ccw order. By overlaying the 2 sets of $O(n)$ intervals
$\\{\Theta(e_{1},M_{12}(e_{1}))-\theta_{p_{1}p_{2}}:\text{ sub-edge
}e_{1}\text{ of }\Gamma_{1}\\}$ and
$\\{\Theta(e_{3},M_{34}(e_{3}))-\theta_{p_{3}p_{4}}:\text{ sub-edge
}e_{3}\text{ of }\Gamma_{3}\\}$, we see that there are at most $O(n)$ choices
of $(e_{1},e_{3})$ such that $\Theta(e_{1},M_{12}(e_{1}))-\theta_{p_{1}p_{2}}$
intersects $\Theta(e_{3},M_{34}(e_{3}))-\theta_{p_{3}p_{4}}$ (mod $\pi$), and
they can be enumerated in $O(n)$ time. The total number of quadruples over all
$O(\log^{2}n)$ choices of $M_{12}$ and $M_{34}$ is $O(n\log^{2}n)$, giving
$O(n\log^{2}n)$ transformations.

∎

Interestingly, Case 2 exploits a different phenomenon than in our earlier
proofs: besides monotone pairings of sub-edges, we have monotone “pairings of
pairs” of sub-edges.

Figure 6: An example quadruple from Case 2 in the proof of Theorem 11. The
pairing $M_{12}$ is produced using $\triangle p_{1}p_{2}p_{4}$ and the pairing
$M_{34}$ is produced using $\triangle p_{2}p_{3}p_{4}$.

###  3.3 Generalizing to $k>4$

Finally, an algorithm for the 4-contact case for general $k$ immediately
follows:

######  Corollary 12.

Given a $k$-gon $P$ and a convex $n$-gon $Q$ in general position, there are at
most $O(k^{4}n\log^{2}n)$ similar copies of $P$ contained in $Q$ that have $4$
different vertices of $P$ on $4$ edges of $Q$, and they can be enumerated in
$\widetilde{O}(k^{5}n)$ time.

###### Proof.

For each of the $O(k^{4})$ choices of vertices $p_{1},p_{2},p_{3},p_{4}$ of
$P$, we generate the $O(n\log^{2}n)$ similarity transformations from Theorem
11 and test the feasibility of each transformation in $O(k\log n)$ time via
binary searches [15]. ∎

##  4 Final Remarks

To keep the presentation cleaner, we have not spelled out the precise
polylogarithmic factors in the time bounds, nor the precise dependencies on
$k$ in the $k^{O(1/\varepsilon)}$ factor, since we believe that extra effort
can help in optimizing those factors. Even without extra effort, if we use
randomized search [10] in the proof of Lemma 3, the number of logarithmic
factors in our $O(n\mathop{\rm polylog}n)$-time algorithm for $k=3$ is only
about 3.

The main question we leave open is whether Problem 1 can be solved in
$O(kn^{1+\varepsilon})$ time for all constant $\varepsilon>0$, which would be
a strict improvement over the previous $\widetilde{O}(kn^{2})$ bound for all
$k$. Similarly, could the number of 4-contact placements of $P$ within $Q$ be
upper-bounded by $\widetilde{O}(kn)$ instead of $\widetilde{O}(k^{4}n)$?

## References

  * [1] Pankaj K. Agarwal, Nina Amenta, and Micha Sharir.  Largest Placement of One Convex Polygon Inside Another.  Discret. Comput. Geom., 19(1):95–104, 1998.  doi:10.1007/PL00009337.
  * [2] 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.  doi:10.1007/PL00009455.
  * [3] Pankaj K. Agarwal and Jeff Erickson.  Geometric Range Searching and Its Relatives.  Contemporary Mathematics, 223:1–56, 1999.  URL: https://jeffe.cs.illinois.edu/pubs/pdf/survey.pdf.
  * [4] Pankaj K. Agarwal and Micha Sharir.  Davenport-Schinzel Sequences and Their Geometric Applications.  In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 1–47. North Holland / Elsevier, 2000\.  doi:10.1016/B978-044482537-7/50002-4.
  * [5] Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, and Micha Sharir.  Subquadratic Algorithms for Some 3SUM-Hard Geometric Problems in the Algebraic Decision-Tree Model.  Comput. Geom., 109:101945, 2023.  doi:10.1016/J.COMGEO.2022.101945.
  * [6] Francis Avnaim and Jean-Daniel Boissonnat.  Polygon Placement Under Translation and Rotation.  RAIRO Theor. Informatics Appl., 23(1):5–28, 1989.  doi:10.1051/ITA/1989230100051.
  * [7] Henry Spalding Baird.  Model-Based Image Matching Using Location.  MIT Press, 1984.
  * [8] Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon.  Subquadratic Algorithms for Algebraic 3SUM.  Discret. Comput. Geom., 61(4):698–734, 2019.  Preliminary version in SoCG 2017.  doi:10.1007/S00454-018-0040-Y.
  * [9] 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.  doi:10.1142/S0218195901000596.
  * [10] Timothy M. Chan.  Geometric Applications of a Randomized Optimization Technique.  Discret. Comput. Geom., 22(4):547–567, 1999.  Preliminary version in SoCG 1998.  doi:10.1007/PL00009478.
  * [11] Timothy M. Chan.  More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems.  ACM Trans. Algorithms, 16(1):7:1–7:23, 2020.  doi:10.1145/3363541.
  * [12] Bernard Chazelle.  The Polygon Containment Problem.  Advances in Computing Research, 1(1):1–33, 1983.  URL: https://www.cs.princeton.edu/~chazelle/pubs/PolygContainmentProb.pdf.
  * [13] L. Paul Chew and Klara Kedem.  A Convex Polygon Among Polygonal Obstacles: Placement and High-Clearance Motion.  Comput. Geom., 3:59–89, 1993.  doi:10.1016/0925-7721(93)90001-M.
  * [14] Karen L. Daniels and Victor Milenkovic.  Multiple Translational Containment. Part I: An Approximate Algorithm.  Algorithmica, 19(1/2):148–182, 1997.  doi:10.1007/PL00014415.
  * [15] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars.  Computational Geometry: Algorithms and Applications.  Springer, 3rd edition, 2008.  URL: https://www.worldcat.org/oclc/227584184.
  * [16] Matthew Dickerson and Daniel Scharstein.  Optimal Placement of Convex Polygons to Maximize Point Containment.  In Proc. 7th ACM-SIAM Symposium on Discrete Algorithm (SODA), pages 114–121, 1996.  URL: http://dl.acm.org/citation.cfm?id=313852.313899.
  * [17] Taekang Eom, Seungjun Lee, and Hee-Kap Ahn.  Largest Similar Copies of Convex Polygons Amidst Polygonal Obstacles.  CoRR, abs/2012.06978, 2020.  arXiv:2012.06978.
  * [18] Allan Grønlund and Seth Pettie.  Threesomes, Degenerates, and Love Triangles.  J. ACM, 65(4):22:1–22:25, 2018.  doi:10.1145/3185378.
  * [19] Daniel M. Kane, Shachar Lovett, and Shay Moran.  Near-Optimal Linear Decision Trees for $k$-SUM and Related Problems.  J. ACM, 66(3):16:1–16:18, 2019.  doi:10.1145/3285953.
  * [20] Marvin Künnemann and André Nusser.  Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union.  In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3181–3201, 2022.  doi:10.1137/1.9781611977073.124.
  * [21] D. T. Lee.  Interval, Segment, Range, and Priority Search Trees.  In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications. Chapman and Hall/CRC, 2004.  doi:10.1201/9781420035179.CH18.
  * [22] Seungjun Lee, Taekang Eom, and Hee-Kap Ahn.  Largest Triangles in a Polygon.  Comput. Geom., 98:101792, 2021.  doi:10.1016/J.COMGEO.2021.101792.
  * [23] Nimrod Megiddo.  Applying Parallel Computation Algorithms in the Design of Serial Algorithms.  J. ACM, 30(4):852–865, 1983.  doi:10.1145/2157.322410.
  * [24] Victor Milenkovic.  Translational Polygon Containment and Minimal Enclosure Using Linear Programming Based Restriction.  In Proc. 28th ACM Symposium on Theory of Computing (STOC), pages 109–118, 1996.  doi:10.1145/237814.237840.
  * [25] Victor Milenkovic.  Multiple Translational Containment. Part II: Exact Algorithms.  Algorithmica, 19(1/2):183–218, 1997.  doi:10.1007/PL00014416.
  * [26] Victor Milenkovic.  Rotational Polygon Containment and Minimum Enclosure Using Only Robust 2D Constructions.  Comput. Geom., 13(1):3–19, 1999.  doi:10.1016/S0925-7721(99)00006-1.
  * [27] Joseph O’Rourke, Subhash Suri, and Csaba D Tóth.  Polygons.  In Handbook of Discrete and Computational Geometry, pages 787–810. CRC Press, 2017.  URL: http://www.csun.edu/~ctoth/Handbook/chap30.pdf.
  * [28] Franco P. Preparata and Michael Ian Shamos.  Computational Geometry: An Introduction.  Texts and Monographs in Computer Science. Springer, 1985.  doi:10.1007/978-1-4612-1098-6.
  * [29] Micha Sharir.  A Near-Linear Algorithm for the Planar 2-Center Problem.  Discret. Comput. Geom., 18(2):125–134, 1997.  Preliminary version in SoCG 1996.  doi:10.1007/PL00009311.
  * [30] Micha Sharir and Sivan Toledo.  External Polygon Containment Problems.  Computational Geometry, 4(2):99–118, 1994.  Preliminary version in SoCG 1991.  doi:10.1016/0925-7721(94)90011-6.

##  Appendix A 2-Contact (2-Anchor) Case

We note that the ideas behind our algorithms in Section 2 for the 3-contact
case can be adapted to handle the 2-contact case as well. In what follows,
suppose that the 2 anchor vertices are $p_{1}$ and $p_{2}$.

###  A.1 Algorithm for $k=3$

We modify the divide-and-conquer algorithm for $k=3$ in Theorem 4. The
algorithm actually becomes simpler, as we only need Lemma 1 but not Lemma 2,
and the range searching sub-problems are simpler (no need for ellipses or
parametric search).

W.l.o.g., assume that the origin $o$ is in the interior of $Q$. For an arc
$\Gamma$ of $Q$ which is delimited by points $u$ and $v$, let
$\Gamma^{\bullet}$ denote the subpolygon bounded by $\Gamma$ and the two rays
$\overrightarrow{ou}$ and $\overrightarrow{ov}$.

Given an interval $S$, the algorithm will find a similarity transformation
$\varphi$, maximizing the scaling factor, such that $\varphi(p_{1})$ is a
vertex $v_{1}$ of $\Gamma_{1}(S)$, $\varphi(p_{2})$ is a vertex $v_{2}$ of
$\Gamma_{2}(S)$, and $\varphi(p_{3})$ is inside $\Gamma_{3}(S)^{\bullet}$.

As before, we partition $S$ into $S^{-}$ and $S^{+}$. The cases are now as
follows:

  * •

Case 1: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{-})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{-})$, and $\varphi(p_{3})$ is inside
$\Gamma_{3}(S^{-})^{\bullet}$. We can recursively solve the problem for
$S^{-}$.

  * •

Case 2: $\varphi(p_{1})$ is on $\Gamma_{1}(S^{+})$, $\varphi(p_{2})$ is on
$\Gamma_{2}(S^{+})$, and $\varphi(p_{3})$ is inside
$\Gamma_{3}(S^{+})^{\bullet}$. We can recursively solve the problem for
$S^{+}$.

  * •

Case 3: $\varphi(p_{2})$ is on $\Gamma_{2}(S^{-})$, and $\varphi(p_{3})$ is
inside $\Gamma_{3}(S^{+})^{\bullet}$. Since
$\Lambda(\Gamma_{2}(S^{-}))+\theta_{p_{1}p_{3}}\subseteq S^{-}$ and
$\Lambda(\Gamma_{3}(S^{+}))+\theta_{p_{1}p_{2}}\subseteq S^{+}$ are disjoint
(mod $\pi$), we can use Lemma 1 to find a sub-arc
$I(v_{1})\subseteq\Gamma_{2}(S)$ for every vertex $v_{1}$ of $\Gamma_{1}(S)$,
such that the condition that $\varphi(p_{3})$ is inside
$\Gamma_{3}(S^{+})^{\bullet}$ is equivalent to the condition that
$\varphi(p_{2})$ is on $I(v_{1})$. (Technically, Lemma 1 works with
$\overleftrightarrow{\Gamma_{3}(S^{+})}$ instead of
$\Gamma_{3}(S^{+})^{\bullet}$, but we can just intersect the sub-arc
$I(v_{1})$ with 2 additional halfplanes that arise from the 2 rays bounding
$\Gamma_{3}(S^{+})^{\bullet}$.)

The problem in this case now reduces to finding a vertex $v_{1}$ of
$\Gamma_{1}(S)$ and a vertex $v_{2}$ of $\Gamma_{2}(S^{-})$, maximizing their
Euclidean distance, such that $v_{2}$ is on $I(v_{1})$. This further reduces
to answering farthest neighbor queries for a 2D point set with an additional
1D interval constraint. Farthest neighbor queries in 2D can be answered
$\widetilde{O}(1)$ time after preprocessing in near-linear time (by point
location in the farthest-point Voronoi diagram [15, 28]). The additional 1D
interval constraints can be handled by multi-leveling with range trees [3, 21]
as before, which increases time bounds by a logarithmic factor.

All remaining cases are symmetric to Case 3 (swapping subscripts 1 and 2
and/or $S^{-}$ and $S^{+}$). The recurrence for the running time remains the
same.

######  Theorem 13.

Given a triangle $P$ and a convex $n$-gon $Q$, we can find the largest similar
copy of $P$ contained in $Q$ that has $2$ vertices of $P$ at $2$ vertices of
$Q$ in $\widetilde{O}(n)$ time.

###  A.2 Algorithm for $k>3$

We can also adapt the algorithm in Theorem 6 to handle the 2-contact case for
general $k$. We use a variant of Lemma 5 where $\varphi(p_{1})$ is a vertex
$v_{1}$ of $\Gamma_{1}$, $\varphi(p_{2})$ is a vertex $v_{2}$ on
$I(v_{1})\subseteq\Gamma_{2}$, and for each $i\in\\{3,\ldots,k\\}$,
$\varphi(p_{i})$ is left of $\overleftrightarrow{\Gamma_{k}}$. The
disjointness conditions for the arcs are the same. The proof is very similar
to that of Lemma 5; however, for each vertex $v_{2}$ on a sub-edge $e_{2}$ of
$\Gamma_{2}$, we redefine

$\begin{array}[]{rrl}{\cal P}(e_{2})\
=&\\{(s,t,u,v)\in\mathbb{R}^{4}:&\mbox{$\varphi_{s,t,u,v}(p_{2})=v_{2}$ and
$\varphi_{s,t,u,v}(p_{i})$ is left of $\overleftrightarrow{M_{i}(e_{2})}$ for
all }\\\\[2.15277pt] &&\mbox{$i\in\\{3,\ldots,k\\}$}\\}\\\\[4.30554pt]
R_{\rho}(e_{2})\ =&\\{\varphi_{s,t,u,v}(p_{1}):&\mbox{$(s,t,u,v)\in{\cal
P}(e_{2})$ and $s^{2}+t^{2}\geq\rho^{2}$}\\}.\end{array}$

Similar to before, ${\cal P}(v_{2})$ is a 2-dimensional polygon in
$\mathbb{R}^{4}$ with $O(k)$ edges (since there are 2 linear equality
constraints and $O(k)$ inequality constraints in 4 variables), and
$R_{\rho}(v_{2})$ is a region in $\mathbb{R}^{2}$ which is the intersection of
a convex $O(k)$-gon and the exterior of an ellipse (actually, a circle in this
case). We partition the region into $O(k)$ constant complexity regions as
before.

The rest of the divide-and-conquer algorithm in Theorem 6 requires no major
changes.

######  Theorem 14.

Given a $k$-gon $P$ and a convex $n$-gon $Q$ (where $k\leq n$), we can find
the largest similar copy of $P$ contained in $Q$ that has $2$ vertices of $P$
at $2$ vertices of $Q$ in $O(k^{O(1/\varepsilon)}n^{1+\varepsilon})$ time for
any $\varepsilon>0$.