# Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation

Mikkel Abrahamsen, Sujoy Bhore, Maike Buchin, Jacobus Conradi, Ce Jin, André Nusser, Carolin Rehs

► To cite this version:

Mikkel Abrahamsen, Sujoy Bhore, Maike Buchin, Jacobus Conradi, Ce Jin, et al. Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation. Symposium on Discrete Algorithms (SODA26), Jan 2026, Vancouver, Canada. hal-05349270

HAL Id: hal-05349270

https://hal.science/hal-05349270v1

Submitted on 5 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation

Mikkel Abrahamsen ⤵ ID
University of Copenhagen, Denmark

Sujoy Bhore ⤵ ID
Indian Institute of Technology Bombay, India

Maike Buchin ⤵ ID
Ruhr University Bochum, Germany

Jacobus Conradi ⤵ ID
University of Bonn, Germany
University of Copenhagen, Denmark

Ce Jin ⤵ ID
Massachusetts Institute of Technology, USA
University of California, Berkeley, USA

André Nusser ⤵ ID
Université Côte d'Azur, CNRS, Inria, France

Carolin Rehs ⤵ ID
Technical University of Dortmund, Germany
Technical University of Eindhoven, The Netherlands

## Abstract

A fundamental problem in shape matching and geometric similarity is computing the maximum area overlap between two polygons under translation. For general simple polygons, the best-known algorithm runs in $O((nm)^2 \log(nm))$ time [Mount, Silverman, Wu '96], where $n$ and $m$ are the complexities of the input polygons. In a recent breakthrough that received the SoCG Best Paper Award 2025, Chan and Hair gave a linear-time algorithm for the special case when both polygons are convex. A key challenge in computational geometry is to design improved algorithms for other natural classes of polygons. We address this by presenting an $O((nm)^{3/2} \log(nm))$-time algorithm for the case when both polygons are orthogonal, probably the most popular class of polygons besides convex and simple ones. This is the first algorithm for polygon overlap on orthogonal polygons that is faster than the almost 30 years old algorithm for general simple polygons.

Complementing our algorithmic contribution, we provide $k$-SUM lower bounds for problems on simple polygons with only orthogonal and diagonal edges. First, we establish that there is no algorithm for polygon overlap with running time $O(\max(n^2, nm^2)^{1-\epsilon})$, where $m \le n$, unless the $k$-SUM hypothesis fails. This matches the running time of our algorithm when $n = m$. We use part of the above construction to also show a lower bound for the polygon containment problem, a popular special case of the overlap problem. Concretely, there is no algorithm for polygon containment with running time $O(n^{2-\epsilon})$ under the 3-SUM hypothesis, even when the polygon to be contained has $m = O(1)$ vertices. Our lower bound shows that polygon containment for these types of polygons (i.e., with diagonal edges) is strictly harder than for orthogonal polygons, and also strengthens the previously known 3-SUM lower bound for polygon containment of [Barequet, Har-Peled '01]. Furthermore, our lower bounds show tightness (up to polylogarithmic factors) of the algorithms of [Avnaim, Boissonnat '89] and [Mount, Silverman, Wu '96] when $m \in O(1)$.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** polygon overlap, polygon containment, algorithm design, lower bound

**Digital Object Identifier** 10.4230/LIPIcs...

<figure><img src="image_2.png" /></figure>

© M. Abrahamsen, S. Bhore, M. Buchin, J. Conradi, C. Jin, A. Nusser and C. Rehs; licensed under Creative Commons License CC-BY 4.0

<figure><img src="image_3.png" /></figure>

LIPICS Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
**XX:2 On the Maximum Overlap of Two Polygons Under Translation**

**Funding** Mikkel Abrahamsen: Supported by Independent Research Fund Denmark, grant 1054-00032B, and by the Carlsberg Foundation, grant CF24-1929.

**Jacobus Conradi:** Supported partially by the iBehave Network: Sponsored by the Ministry of Culture and Science of the State of North Rhine-Westphalia, and the Carlsberg Foundation, grant CF24-1929.

**Ce Jin:** Supported by the Jane Street Graduate Research Fellowship, NSF grant CCF-2330048, and a Simons Investigator Award.

**André Nusser:** Supported by the France 2030 investment plan managed by the ANR as part of the Initiative of Excellence of Université Côte d'Azur with reference number ANR-15-IDEX-01.

**Carolin Rehs:** Partly supported by the PRIME programme of the German Academic Exchange Service (DAAD) with funds from the German Federal Ministry of Research, Technology and Space (BMFTR)

**1 Introduction**

We consider the problem of computing the *maximum overlap* of two polygons $P$ and $Q$ with $n$ and $m$ vertices, respectively, i.e., finding a translation $\tau = (\tau_x, \tau_y) \in \mathbb{R}^2$ such that the area of $P \cap (Q + \tau)$ is maximum. This can be seen as a formalization of matching the shapes $P$ and $Q$, and the maximum overlap is a natural similarity measure: the larger it is relative to the areas of $P$ and $Q$, the more similar they are. The problem was first studied by Mount, Silverman and Wu [16] for general simple polygons. They show that the overlap function $\tau \mapsto \text{area}(P \cap (Q + \tau))$ is a continuous and piecewise polynomial surface of degree at most two, consisting of $O((nm)^2)$ pieces. Furthermore, they give an example of two orthogonal polygons (for arbitrary values of $n$ and $m$) that realize the bound, i.e., the complexity of the overlap function is $\Omega((nm)^2)$, and hence the bound is tight in the worst-case. They also describe an algorithm to compute the entire function within the same bound $O((nm)^2)$ on the running time, which yields an $O((nm)^2 \log(nm))$ algorithm for the polygon overlap problem. They posed the open question whether an algorithm with better running time exists. Approximation algorithms for finding the maximum overlap are described in [7, 7, 13]. See also the survey [17] on polygons from the handbook of discrete and computational geometry for an overview.

A prominent special case is when both polygons are convex, for which the bound $O(m^2+n^2+mn \cdot \min(m,n))$ on the complexity of the overlap function was given in [16]. De Berg, Cheong, Devillers, van Kreveld, and Teillaud [9] describe an algorithm that computes the maximum overlap of two convex polygons in time $\tilde{O}(n+m)$ ($\tilde{O}(\cdot)$ hides logarithmic factors in $n$ and $m$). This was improved recently by Chan and Hair in a celebrated paper [5] that received the SoCG Best Paper Award 2025. They describe a randomized algorithm with $O(n+m)$ expected running time.

In this paper, we consider the problem for another well-studied subclass of simple polygons, where both $P$ and $Q$ are orthogonal polygons, i.e., simple polygons where every edge is either horizontal or vertical:

**► Problem 1 (ORTHMAXOVERLAP).** Let $P$ and $Q$ be two orthogonal polygons with $n$ and $m$ vertices respectively. Find $\tau \in \mathbb{R}^2$ such that area($P \cap (Q + \tau)$) is maximum.

<footnote n="1">¹ The class of *octilinear* polygons is the subclass of simple polygons whose edges are at an angle $k \frac{\pi}{4}$ for $0 \le k < 8$. We remark that the lower bound requires only six out of all eight edge angles, and the class of orthogonal polygons is trivially contained in the class of octilinear polygons.</footnote>
<table><caption>**Table 1** Upper and lower bounds for problems related to ORTHMAXOVERLAP.</caption><thead><tr><th>Polygon Type</th><th>Objective</th><th>Lower Bound</th><th>Upper Bound</th></tr></thead><tbody><tr><td rowspan="2">CONVEX</td><td>CONTAINMENT</td><td>Ω(n + m)</td><td>O(n + m) [5]</td></tr><tr><td>MAXOVERLAP</td><td>Ω(n + m)</td><td>O(n + m) [5]</td></tr><tr><td rowspan="2">ORTHOGONAL</td><td>CONTAINMENT</td><td>O((nm)<sup>1-ε</sup>) [15]</td><td>Ο(nm) [14]</td></tr><tr><td>MAXOVERLAP</td><td>O((nm)<sup>1-ε</sup>) [15]</td><td>Ο((nm)<sup>3/2</sup>)<br>Theorem 1</td></tr><tr><td rowspan="3">OCTOLINEAR<sup>1</sup><br>or<br>SIMPLE</td><td>CONTAINMENT</td><td>O(n<sup>2-ε</sup>)<br>Theorem 4</td><td>Ο((nm)<sup>2</sup>) [2]</td></tr><tr><td rowspan="2">MAXOVERLAP</td><td>O(max(n<sup>2</sup>, nm<sup>2</sup>)<sup>1-ε</sup>)<br>Theorem 3</td><td rowspan="2">Ο((nm)<sup>2</sup>) [2]</td></tr><tr><td>m = Θ(n): O((nm)<sup>(3/2)-ε</sup>)</td></tr></tbody></table>

For this problem, we give the first improvement over the nearly three decades old $O((nm)^2 \log(nm))$ bound from [16]. In particular, we prove the following theorem.

**Theorem 1.** Let $P$ and $Q$ be orthogonal polygons with $n$ and $m$ vertices, respectively. There is an algorithm for computing the translation $\tau$ maximizing the overlap area($P \cap (Q + \tau)$) in time $O((nm)^{3/2} \log(nm))$.

We complement our algorithm by a conditional lower bound via the $k$-SUM problem.

**Problem 2 (k-SUM).** Given $k$ sets of positive integers $A_1, A_2, \dots, A_k$ of size $n$ each, is there $(a_1, \dots, a_k) \in A_1 \times \dots \times A_k$ such that $a_1 = \sum_{i \ge 2}^{k} A_i$?

The corresponding hardness assumption in fine-grained complexity theory is the $k$-SUM-Hypothesis [1, 12]:

**Definition 2 (k-SUM Hypothesis).** For any integer $k$ the $k$-SUM problem cannot be solved in $O(n^{\lceil k/2 \rceil - \varepsilon})$ time for any $\varepsilon > 0$.

We provide the following lower bound for any algorithm solving the maximum overlap problem for simple polygons, assuming the $k$-SUM hypothesis.

**Theorem 3.** Let $P$ and $Q$ be polygons with $n$ and $m$ vertices, respectively, where $m \le n$ and $\delta \in \mathbb{R}^+$. Assume that all edges of $P$ and $Q$ are either horizontal, vertical or parallel to the diagonal. Assuming the $k$-SUM hypothesis, deciding whether there is a translation $\tau$ such that area($P \cap (Q + \tau)$) > $\delta$ cannot be solved in $O((\max(n^2, nm^2))^{1-\varepsilon})$ time for any $\varepsilon > 0$.

Our reduction can also be modified to obtain a lower bound for the *polygon containment* problem. While this problem is a special case of the *maximum overlap* problem, it has attracted more attention than the overlap problem. In the containment problem we want to know whether there is some $\tau \in \mathbb{R}^2$ so that $(Q+\tau) \subset P$ and thus area($P \cap (Q+\tau)$) = area($Q$). This problem was first studied by Chazelle in 1983 [6], followed by numerous other results. Of particular interest, we only mention the results when both $P$ and $Q$ are simple or orthogonal polygon and only translations are allowed; a plethora of results exist when rotations are allowed and for more restricted variants such as when one or both of the polygons are convex; for exhaustive literature reviews on the problem, see the recent papers [15, 4]. Avnaim and
XX:4 On the Maximum Overlap of Two Polygons Under Translation

Boissonnat [2] gave an algorithm for solving polygon containment of two simple polygons in $O((nm)^2 \log(nm))$ time. Hernández-Barrera [14] improved the running time to $O((nm)^2)$ and solved the case where both $P$ and $Q$ are orthogonal in $O(nm \log(nm))$ time.

As for known lower bounds, Barequet and Har-Peled [3] showed that when $P$ and $Q$ both have $n$ vertices, no algorithm has running time $O(n^{2-\epsilon})$ under the 3-SUM hypothesis. Künnemann and Nusser [15] gave various conditional lower bounds for polygon containment and the more general largest scaled containment problem, which is to find the largest homothet (i.e., scaled copy) of $Q$ that fits in $P$. For polygon containment, they showed that when $P$ and $Q$ are orthogonal and have arbitrary numbers $n$ and $m$ of vertices, then no algorithm has running time $O((nm)^{1-\epsilon})$ time under the Orthogonal Vectors (OV) hypothesis. Assuming the 4-SUM hypothesis, they showed that for the largest scaled containment problem, no algorithm has running time $O(n^{2-\epsilon})$, even when both $P$ and $Q$ are orthogonal and $m = O(1)$.

We improve on these lower bounds by simplifying the reduction behind Theorem 3 to show the following.

**Theorem 4.** Let $P$ and $Q$ be polygons with $n$ and $O(1)$ vertices, respectively. Assume that all edges of $P$ and $Q$ are either horizontal, vertical or parallel to the diagonal. Assuming the 3-SUM hypothesis, deciding whether there is a translation for $Q$ such that $Q$ is contained in $P$ cannot be solved in $O(n^{2-\epsilon})$ time for any $\epsilon > 0$.

We summarize all our results in context in Table 1, and highlight below some key consequences of our theorems:

- The arrangement that is constructed for the polygon overlap problem in [16] has worst-case size $\Theta((nm)^2)$, even for orthogonal polygons. We break this natural barrier with our $O((nm)^{3/2} \log nm)$ running time.

- Besides improving the known lower bounds for polygon containment for any $m = O(n^\alpha)$ with $\alpha < 1$, we give the first non-trivial lower bound for polygon containment in the regime where $m \in O(1)$, improving the previous lower bounds from $O(n^{1-\epsilon})$ to $O(n^{2-\epsilon})$.

- We show that polygon containment with edges in three directions (orthogonal and one diagonal) is strictly harder than polygon containment with edges in two directions (orthogonal): we prove that the former cannot be solved in $O(n^{2-\epsilon})$ time when $m \in O(1)$, while the latter is solvable in near-linear time in this setting.

- With our improved lower bounds, we show that the decades-old algorithms of [2, 16, 14] for polygon overlap and containment are all tight up to polylogarithmic factors for $m \in O(1)$.

1.1 Technical Overview

We first give an overview of our techniques used to obtain our results.

**Upper bound** Let $P$ and $Q$ be two orthogonal polygons with $n$ and $m$ vertices respectively. We give the first algorithm improving on the original $O((nm)^2)$ algorithm from Mount, Silverman and Wu [16] for non-convex polygons. That is, for the subclass of orthogonal polygons we give an $\tilde{O}((nm)^{3/2})$ algorithm.

Similar to the approach presented in [16], we consider the piecewise polynomial surface of degree at most two describing the function $\tau \mapsto \text{area}(P \cap (Q+\tau))$. We observe that the function splits into $O(nm)$ rectangles, each with their own bilinear function, and $\tau \mapsto \text{area}(P \cap (Q+\tau))$ can be expressed as the sum of bilinear functions of rectangles containing $\tau$. We may now sweep over these rectangles to compute the translation maximizing the intersection of $P$ and $Q + \tau$ in $\tilde{O}((nm)^2)$ time. We improve this sweep-line algorithm with a batching technique
which groups events for the sweep-line algorithm into $O(\sqrt{nm})$ groups of size $O(\sqrt{nm})$ in both x- and y-direction resulting in $O(nm)$ small windows in which we identify the maximizing translation in $\tilde{O}(\sqrt{nm})$ time as follows: Via algebraic manipulations we rewrite the partial sums of bilinear functions, as they would have been encountered and evaluated by the sweep-line algorithm, into a set $V$ of $O(\sqrt{nm})$ vectors in $\mathbb{R}^3$. Identifying the maximum among the $O(nm)$ candidate translations in the small window then reduces to $O(\sqrt{nm})$ extreme-point queries on the set $V$ which, as $V \subset \mathbb{R}^3$, can be answered in $\tilde{O}(\sqrt{nm})$ total time, via the convex hull of $V$. The result is an algorithm with running time in $\tilde{O}((nm)^{3/2})$.

Comparing our techniques to the algorithm given by Mount, Silverman and Wu [16], we observe that our approach is similar in spirit in that we consider the piecewise polynomial surface of degree at most two describing the function $\tau \mapsto \text{area}(P \cap (Q + \tau))$. As noted in Section 1, Mount, Silverman and Wu showed that the overlap function can have complexity $\Omega((nm)^2)$ even for orthogonal polygons, so their method of explicitly computing the polynomial surface is unlikely to yield improved bounds. Unlike their algorithm, however, we manage to circumvent the explicit computation of the polynomial surface represented as the sum of bilinear polynomials defined on rectangular regions via our novel recast to extreme-point queries to a three-dimensional convex hull. With this, we improve the running time of the algorithm given by Mount, Silverman and Wu by a factor of $\sqrt{nm}$.

Overall, our techniques reduce a geometric problem to an algebraic problem, which we recast into a geometric problem to solve efficiently. Interestingly, there is very little conceptual overlap between the initial geometric problem and the final recast, and little intuition can be gathered from the set $V$ for the underlying ORTHMAXOVERLAP instance.

## Lower bounds
We complement our algorithm by giving lower bounds for the polygon overlap and for the polygon containment problem. We reduce to the polygon overlap problem from an imbalanced variant of 5-SUM. In this variant, we are given five sets $A, B, C, D$, and $E$ with $|A| = |B| = |C| = n$ and $|D| = |E| = m$, and we want to decide whether there exist elements $(a, b, c, d, e) \in A \times B \times C \times D \times E$ such that $a = b + c + d + e$. We show that this problem cannot be solved in time $O(\max(n^2, nm^2)^{1-\epsilon})$ unless the $k$-SUM Hypothesis fails.

Let us now sketch our reduction from this problem to the maximum overlap problem. We observe that, for two comb-like polygons with their prongs oriented downward, the translation $\tau = (\tau_x, \tau_y)$ maximizing the overlap between both polygons aligns one prong from the translated polygon $Q$ with one prong of the fixed polygon $P$. If the two aligned prongs are at $x$-coordinate $-d$ and $b$, then the $x$-coordinate of the translation satisfies the equation $\tau_x = b+d$. Hence, by carefully spacing the prongs of the combs and creating a similar construction for the $y$-coordinate, we can restrict any translation aligning both pairs of combs at once to $\tau_x = b_i+d_k$ and $\tau_y = c_j+e_\ell$ for any $b_i \in B, c_j \in C, d_k \in D$ and $e_\ell \in E$. We now add a diagonal comb to the fixed polygon $P$, where every prong is placed at the (anti-)diagonal line $x+y=a_h$ for $a_h \in A$, and a single prong to $Q$ at $x+y=0$. These prongs are only aligned for translations of the form $\tau_x + \tau_y = a_h$. Then, if $\tau$ is a translation such that all three pairs of combs are aligned properly, we obtain $\tau_x = b_i+d_k, \tau_y = c_j+e_\ell$, and $\tau_x + \tau_y = a_h$, which implies a solution to the 5-SUM instance. The polygons $P$ and $Q$ have $O(n)$ and $O(m)$ vertices respectively. When each comb of $Q$ only has one prong, the construction extends to polygon containment, giving a lower bound based on 3-SUM.

Comparing our techniques with the techniques of the 3-SUM hypothesis based lower bound from Barequet and Har-Peled [3] and the Orthogonal Vectors hypothesis based lower bound from Künnemann and Nusser [15] for the ORTHMAXOVERLAP problem, we observe the following: Both their techniques essentially consider only one pair of combs, restricting
XX:6 On the Maximum Overlap of Two Polygons Under Translation

<figure><img src="image_4.png" /><figcaption>■ **Figure 1** Illustration of the support of the function area($P \cap (Q + (x, y))$), and how it partitions into $O(1)$ (half-open disjoint) rectangular regions.</figcaption></figure>

the set $\tau = (\tau_x, \tau_y)$ of translations such that $Q + \tau$ is contained in $P$ to one of $nm$ possible $x$-translations. Combining this with a second set of combs restricting the $y$-translations is straight-forward, however, there is no interdependence between $\tau_x$ and $\tau_y$, as both combs can be aligned independently of one another, giving $O(nm)$ instead of the desired $O((nm)^2)$ translations that ‘need to be checked’. This problem is addressed in the 4-SUM lower bound of [15] by considering scalings additionally to translations, to determine the biggest copy of $Q$ in $P$. This additional degree of freedom allows to encode more complexity, however, at the cost of showing a lower bound for a more general problem (hence, a weaker bound). In our work, we address this issue by introducing diagonal combs which encode equations of the form $\tau_x + \tau_y = C$ for some constant $C$. That allows us to couple $\tau_x$ and $\tau_y$ to one another such that the two axis-aligned combs cannot be aligned independently from each other.

2 Rectangles and Unions of Rectangles

We first discuss a simple sweep-line based algorithm which solves ORTHMAXOVERLAP in $\tilde{O}((nm)^2)$ total time, by partitioning both polygons into a set of rectangles and restricting the solution space to $O((nm)^2)$ candidate translations. This sweep-line based algorithm serves as the basis for an improved algorithm which we present in Section 3. We begin by analyzing the function $\tau \mapsto \text{area}(P \cap (Q + \tau))$, where $P$ and $Q$ are rectangles.

For this, define for two sets $A$ and $B$ in $\mathbb{R}$, the set $A - B := \{a - b \mid (a, b) \in A \times B\}$. Let further $\lambda(\cdot)$ be the Lebesgue measure, which we use to measure the length of intervals in $\mathbb{R}$.

► **Lemma 5.** Let $P = [l_P, r_P] \times [b_P, t_P]$ and $Q = [l_Q, r_Q] \times [b_Q, t_Q]$ be two rectangles. There are 9 disjoint half-open rectangles $[l_i, r_i) \times [b_i, t_i)$ and real values $A_i, B_i, C_i$ and $D_i$ computable in $O(1)$ time such that $l_i, r_i \in \{l_P, r_P\} - \{l_Q, r_Q\}$ and $b_i, t_i \in \{b_P, t_P\} - \{b_Q, t_Q\}$ and

$$ \text{area}(P \cap (Q + (x, y))) = \begin{cases} A_i + B_i x + C_i y + D_i xy, & \text{if } (x, y) \in [l_i, r_i) \times [b_i, t_i) \text{ for } i \le 9 \\ 0, & \text{otherwise.} \end{cases} $$

**Proof.** For the proof refer to Figure 1. Observe that

$$ \text{area}(P \cap (Q + (x, y))) = \lambda([l_P, r_P] \cap [l_Q + x, r_Q + y]) \cdot \lambda([b_P, t_P] \cap [b_Q + y, t_Q + y]). $$
The continuous function $x \mapsto \lambda([l_P, r_P] \cap [l_Q + x, r_Q + x])$ is a convolution of two one-dimensional interval membership functions and as such can be described by (at most) three disjoint half-open intervals $[l_i, r_i)$ and values $A_i$ and $B_i$ such that

$$ \lambda([l_P, r_P] \cap [l_Q + x, r_Q + x]) = \begin{cases} A_i + B_i x, & \text{if } x \in [l_i, r_i) \text{ for } i \le 3 \\ 0, & \text{otherwise,} \end{cases} $$

where $l_i, r_i \in \{l_P, r_P\} - \{l_Q, r_Q\}$. Similarly there are (at most) three disjoint half-open intervals $[b_i, t_i)$ and values $C_i$ and $D_i$ such that

$$ \lambda([b_P, t_P] \cap [b_Q + y, t_Q + y]) = \begin{cases} C_i + D_i y, & \text{if } x \in [b_i, t_i) \text{ for } i \le 3 \\ 0, & \text{otherwise,} \end{cases} $$

with $b_i, t_i \in \{b_P, t_P\} - \{b_Q, t_Q\}$. Hence, the fact that $(A_i + B_i x) \cdot (C_j + D_j y) = A_i C_j + B_i C_j x + A_i D_j y + B_i D_j xy$ for $i, j \le 3$ implies the claim. Finally, all values can be computed in $O(1)$ time concluding the proof. ◀

**Corollary 6.** Let $P = [l_P, r_P] \times [b_P, t_P]$ and $Q = [l_Q, r_Q] \times [b_Q, t_Q]$ be two rectangles. There are 18 rectangular half-open regions $[l_i, r_i) \times [b_i, \infty)$ together with real values $A_i, B_i, C_i$ and $D_i$ computable in $O(1)$ time such that

$$ \text{area}(P \cap (Q + (x, y))) = \sum_{i} 1[(x, y) \in [l_i, r_i) \times [b_i, \infty)] (A_i + B_i x + C_i y + D_i xy) $$

Further, $l_i, r_i \in \{l_P, r_P\} - \{l_Q, r_Q\}$ and $b_i \in \{b_P, t_P\} - \{b_Q, t_Q\}$.

**Proof.** This is an immediate consequence of Lemma 5 together with the fact that for any $l_i, r_i, b_i, t_i, A_i, B_i, C_i, D_i, x$ and $y$ it holds that

$$ \begin{aligned} & 1[(x, y) \in [l_i, r_i) \times [b_i, t_i)](A_i + B_i x + C_i y + D_i xy) \\ &= 1[(x, y) \in [l_i, r_i) \times [b_i, \infty)](A_i + B_i x + C_i y + D_i xy) \\ & \quad - 1[(x, y) \in [l_i, r_i) \times [t_i, \infty)](A_i + B_i x + C_i y + D_i xy). \end{aligned} \quad \text{◀} $$

Next we show that the maximum of $\tau \mapsto \text{area}(P \cap (Q + \tau))$ for orthogonal polygons $P$ and $Q$ is attained by one of only $O((nm)^2)$ easily computable candidate translations.

**Lemma 7.** Let $P$ be an orthogonal polygon with $n$ vertices. In $O(n \log n)$ time one can compute $O(n)$ interior-disjoint rectangles $R_i$ such that $P = \cup_i R_i$. Further the coordinates of $R_i$ are a subset of the coordinates of $P$.

**Proof.** This can be achieved via standard techniques, first sorting all the input coordinates according to their $y$-coordinate and then shooting horizontal rays from every reflex vertex (i.e., a vertex with interior angle $3\pi/2$), cutting the polygon into $O(n)$ horizontal slabs, where every vertex defining such a slab is either an input vertex, or the intersection of a vertical edge of $P$ with a horizontal ray rooted at a reflex vertex. As such every point is comprised of coordinates of the input polygon. ◀

**Lemma 8.** Let $P$ and $Q$ be orthogonal polygons. Let $P_x, P_y, Q_x$ and $Q_y$ be the set of $x$- and $y$-coordinates of $P$ and $Q$ respectively. For $X = P_x - Q_x$ and $Y = P_y - Q_y$ it holds that

$$ \max_{\tau \in \mathbb{R}^2} \text{area}(P \cap (Q + \tau)) = \max_{(x,y) \in X \times Y} \text{area}(P \cap (Q + (x, y))). $$
XX:8 On the Maximum Overlap of Two Polygons Under Translation

**Proof.** By Lemma 5 and Lemma 7 there are $O(nm)$ rectangular half-open disjoint regions $[l_i, r_i) \times [b_i, t_i)$ together with real values $A_i, B_i, C_i$ and $D_i$ such that for any $(x, y) \in \mathbb{R}^2$

$$ \text{area}(P \cap (Q + (x, y))) = \sum_{i} 1[(x, y) \in [l_i, r_i) \times [b_i, t_i)] \cdot (A_i + B_i x + C_i y + D_i xy), $$

with $l_i, r_i \in X$ and $b_i, t_i \in Y$. Let now $\tau^* = (x^*, y^*)$ be such that area$(P \cap (Q + \tau^*)) = \max_{\tau \in \mathbb{R}^2} \text{area}(P \cap (Q + \tau))$. Assume that $x^* \notin X$. We will show that there is some $\hat{x} \in X$ such that for $\hat{\tau} = (\hat{x}, y^*)$ it holds that area$(P \cap (Q + \hat{\tau})) \ge \text{area}(P \cap (Q + \tau^*))$. Note that this, together with a symmetric argument for the y-coordinate, implies the claim.

As $x^*$ is not in $X$, there are two consecutive elements $x_l, x_r \in X$ with $x_l < x^* < x_r$. Let $\mathcal{R}$ be the set of all indices $i$ such that $\tau^*$ is in the half-open disjoint regions $[l_i, r_i) \times [b_i, t_i)$. Thus for all $x \in [x_l, x_r)$ it holds that

$$ \text{area}(P \cap (Q + (x, y^*))) = \sum_{i \in \mathcal{R}} (A_i + B_i x + C_i y^* + D_i xy^*) $$

In fact, by continuity of $\tau \mapsto \text{area}(P \cap (Q + \tau))$ this even holds for all $x \in [x_l, x_r]$. Let $B = \sum_{i \in \mathcal{R}} B_i$ and $D = \sum_{i \in \mathcal{R}} D_i$. As $\frac{\partial}{\partial x}\text{area}(P \cap (Q + (x, y^*))) = B + Dy^*$ is constant for all $x \in (x_l, x_r)$, at least one of area$(P \cap (Q + (x_l, y^*)))$ and area$(P \cap (Q + (x_r, y^*)))$ is at least area$(P \cap (Q + (x^*, y^*)))$. As both $x_l$ and $x_r$ are in $X$, this implies the claim. $\quad$

Next, we represent the function $\tau \mapsto \text{area}(P \cap (Q + \tau))$ via $O(nm)$ translation slabs, i.e., unbounded rectangular areas $[l, r) \times [b, \infty)$ endowed with a bilinear function, such that the function $\tau \mapsto \text{area}(P \cap (Q + \tau))$ is the sum of bilinear functions of translation slabs containing $\tau$ evaluated at $\tau$.

**Definition 9 (translation slabs).** Let $P$ and $Q$ be two orthogonal polygons. A set of half-open rectangles $\{[l_i, r_i) \times [b_i, \infty) \mid i \in I\}$ each endowed weights $A_i, B_i, C_i$, and $D_i$ for $i \in I$ is called a set of translation slabs of $P$ and $Q$ if for every $(x, y) \in \mathbb{R}^2$

$$ \text{area}(P \cap (Q + (x, y))) = \sum_{i \in I} 1[(x, y) \in [l_i, r_i) \times [b_i, \infty)] \cdot (A_i + B_i x + C_i y + D_i xy). $$

**Lemma 10.** Let $P$ and $Q$ be two orthogonal polygons with $n$ and $m$ vertices. Let $P_x, P_y, Q_x$ and $Q_y$ be the set of $x$- and $y$-coordinates of $P$ and $Q$ respectively. Let $X = P_x - Q_x$, $Y = P_y - Q_y$. There is an algorithm which computes a set of $O(nm)$ translation slabs of $P$ and $Q$ in $O(nm + (n+m)\log(n+m))$ time, where every translation slab is defined by $l, r \in X$ and $b \in Y$ as $[l, r) \times [b, \infty)$.

**Proof.** Via Lemma 7, the algorithm first computes a decomposition of $P$ and $Q$ into $O(n)$ and $O(m)$ rectangles in $O((n+m)\log(n+m))$ total time. By slight abuse of notation let us assume that they are exactly $n$ and $m$ rectangles. Let $P_1, \dots, P_n$ be the rectangles from the decomposition of $P$ and $Q_1, \dots, Q_m$ be the rectangles from the decomposition of $Q$. Then for every $(x, y) \in \mathbb{R}^2$

$$ \text{area}(P \cap (Q + (x, y))) = \sum_{i=1}^{n} \sum_{j=1}^{m} \text{area}(P_i \cap (Q_j + (x, y))). $$

For every $i \le n$ and $j \le m$, let $R_{i,j,1}, \dots, R_{i,j,K}$ be the $K \le 18$ rectangular half-open regions from Corollary 6 with values $A_{i,j,k}, B_{i,j,k}, C_{i,j,k}$ and $D_{i,j,k}$ for $1 \le k \le K$. Then

$$ \text{area}(P \cap (Q + (x, y))) = \sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{k=1}^{K} 1[(x, y) \in R_{i,j,k}] (A_{i,j,k} + B_{i,j,k}x + C_{i,j,k}y + D_{i,j,k}xy). $$
Note that by Lemma 7 these translation slabs can be computed in time $O(nm + (n+m)\log(n+m))$ total time. ◀

Finally, with the representation of $\tau \mapsto \text{area}(P \cap (Q + \tau))$ from Lemma 10, we present an algorithm solving ORTHMAXOVERLAP in $\tilde{O}((nm)^2)$ time. For this, denote the set of translation slabs output by the algorithm from Lemma 10 by $\mathcal{R}(P,Q)$, where $R \in \mathcal{R}(P,Q)$ is endowed with the weights $A_R, B_R, C_R$ and $D_R$. Note that $\mathcal{R}(P,Q)$ is a set of rectangular regions in translation space, unlike the set of rectangles obtained by the decomposition of both P and Q via Lemma 7.

**Lemma 11.** Let P and Q be orthogonal polygons with n and m vertices respectively. Let $P_x, P_y, Q_x$ and $Q_y$ be the set of x- and y-coordinates of P and Q respectively. Let $X = P_x - Q_x$, $Y = P_y - Q_y$ and let $Q \subset X \times Y$ be given. There is an algorithm that for every $q \in Q$ computes $A_q = \sum_{R \in \mathcal{R}(P,Q)} \mathbb{1}[q \in R]A_R$, $B_q = \sum_{R \in \mathcal{R}(P,Q)} \mathbb{1}[q \in R]B_R$, $C_q = \sum_{R \in \mathcal{R}(P,Q)} \mathbb{1}[q \in R]C_R$, and $D_q = \sum_{R \in \mathcal{R}(P,Q)} \mathbb{1}[q \in R]D_R$, in total time $O(nm \log(nm) + |Q| \log(nm))$.

**Proof.** We imagine sweeping a horizontal line from $-\infty$ to $\infty$ over the values of Y. During this sweep we maintain a binary tree with leaves corresponding to the values in X. For any node v of the tree let $X_v$ be the set of leaves in the tree rooted at v. At a given sweep line event y for a given node v with parent p let $\mathcal{R}_v$ be the subset of the translations slabs $R \in \mathcal{R}(P,Q)$ such that $X_v \times \{y\} \subset R$ and $X_p \times \{y\} \not\subset R$. For any node v we maintain the values $A_v = \sum_{r \in \mathcal{R}_v} A_r$, $B_v = \sum_{r \in \mathcal{R}_v} B_r$, $C_v = \sum_{r \in \mathcal{R}_v} C_r$ and $D_v = \sum_{r \in \mathcal{R}_v} D_r$. Observe that initially all $A_v = B_v = C_v = D_v = 0$ can correctly be computed. Now, at every sweep-line event y for every $R = [l, r) \times [b, \infty) \in \mathcal{R}(P,Q)$ such that $b = y$ we add $A_R, B_R, C_R$ and $D_R$ to $A_v, B_v, C_v$ and $D_v$ of the roots v of the $O(\log(nm))$ maximal subtrees contained in $[l, r)$ maintaining the values correctly, as by Lemma 7 every translation slab has its lower boundary at some $y \in Y$. This maintenance takes $O(nm \log(nm))$ total time.

For $y \in Y$ let $Q_y$ be the subset of elements $q = (q_x, q_y)$ in Q such that $q_y = y$. When the sweep-line has finished handling all translation slabs whose lower boundary is y, we can output $A_q, B_q, C_q$ and $D_q$ for any $q = (q_x, q_y) \in Q_y$ by traversing the tree from root to the leaf representing $q_x$ summing all $A_v, B_v, C_v$ and $D_v$ along the path. As this path has length $O(\log(nm))$, the values $A_q, B_q, C_q$ and $D_q$ can be computed in time $O(\log(nm))$ per element in $Q_y$ and hence Q throughout the entire sweep-line algorithm concluding the proof. ◀

**Corollary 12.** Let P and Q be orthogonal polygons with n and m vertices respectively. There is an algorithm that computes $\max_{\tau \in \mathbb{R}^2} \text{area}(P \cap (Q + \tau))$ in $O((nm)^2 \log(nm))$ time.

**Proof.** Let $P_x, P_y, Q_x$ and $Q_y$ be the set of x- and y-coordinates of P and Q respectively. Let $X = P_x - Q_x$, $Y = P_y - Q_y$. By Lemma 8, the maximum is attained by a translation $\tau \in X \times Y$. The claim is then a consequence of Lemma 11 by setting $Q \leftarrow X \times Y$. This gives us for every $q = (x, y) \in X \times Y$ values $A_q, B_q, C_q$ and $D_q$ such that $\text{area}(P \cap (Q + q)) = A_q + B_qx + C_qy + D_qxy$ can be evaluated in $O(1)$ time, concluding the proof. ◀

### 3 An $O((nm)^{3/2} \log(nm))$ Algorithm

In this section we give critical insights that allow batching queries, improving on the algorithm given in Corollary 12. The improved algorithm splits the set $X \times Y$ from Lemma 8 into $O(\sqrt{nm})$ horizontal strips $X \times Y_\beta$ each $Y_\beta$ containing $O(\sqrt{nm})$ elements of Y. In each such strip there are $O(\sqrt{nm})$ lower boundaries of translation slabs $[l_i, r_i) \times [b_i, \infty) \in \mathcal{R}(P,Q)$. The corresponding intervals $[l_i, r_i)$ split $X \times Y_\beta$ into vertical strips $X_\alpha \times Y_\beta$, each
XX:10 On the Maximum Overlap of Two Polygons Under Translation

containing $O(\sqrt{nm})$ elements of $X$ on average. For each such $X_\alpha \times Y_\beta$, we encode $Y_\beta$ in a three dimensional convex hull. For any $x \in X_\alpha$, we need to find the $y \in Y_\beta$ realizing $\max_{y \in Y_\beta}$ area($P \cap (Q + (x, y))$). This then amounts to computing an extreme point of the convex hull 'in the direction of x'. Importantly, in three dimensions one can compute and store the convex hull in near-linear time allowing extreme-point queries in logarithmic time.

**Lemma 13** ([10, 11]). Given $n$ points $p_1, \dots, p_n$ in $\mathbb{R}^3$ one can compute in $O(n \log n)$ time a data structure that can answer extreme point queries for points $q \in \mathbb{R}^3$ of the form $\arg\max_i \langle p_i, q \rangle$ in time $O(\log n)$.

**Lemma 14.** Let $P$ and $Q$ be orthogonal polygons with $n$ and $m$ vertices respectively. Algorithm 1 provided with $P$ and $Q$ computes some $\tau^* \in \mathbb{R}^2$ and $A^* \in \mathbb{R}$ such that $\tau^*$ attains the maximum overlap $\max_{\tau \in \mathbb{R}^2} \text{area}(P \cap (Q + \tau)) = A^* = \text{area}(P \cap (Q + \tau^*))$.

*Proof.* By Lemma 8 it suffices for the algorithm to compute $\max_{\tau' \in X \times Y} \text{area}(P \cap (Q + \tau'))$.

First observe that $Y$ in line 6 can indeed be partitioned as claimed via a linear scan of $Y$ as there are a total of $O(nm)$ translation slabs in $\mathcal{R}(P, Q)$. Hence after line 8 $Y_{\text{heavy}}$ and all $Y_\beta$ together partition $Y$, where each $Y_\beta$ is a contiguous subset of $Y$. Lemma 11 implies that after line 9 and line 10 $A$ stores $\text{area}(P \cap (Q + \tau)) = \max_{\tau' \in X \times Y_{\text{heavy}}} \text{area}(P \cap (Q + \tau'))$.

**Algorithm 1** Maximum Polygon Overlap

1: **procedure** MAXRECTPOLYGONOVERLAP($P, Q$)

2: &nbsp;&nbsp;&nbsp;&nbsp;Let $P_x, P_y, Q_x$ and $Q_y$ be the set of $x$- and $y$-coordinates of $P$ and $Q$ respectively

3: &nbsp;&nbsp;&nbsp;&nbsp;Let $X \leftarrow P_x - Q_x, Y \leftarrow P_y - Q_y$, and store them in sorted lists

4: &nbsp;&nbsp;&nbsp;&nbsp;Compute the set of translation slabs $\mathcal{R}(P, Q)$ together with its weights

5: &nbsp;&nbsp;&nbsp;&nbsp;Associate every translation slab $[l, r) \times [b, \infty) \in \mathcal{R}(P, Q)$ to $b \in Y$

6: &nbsp;&nbsp;&nbsp;&nbsp;Partition $Y$ into $C = O(\sqrt{|P||Q|})$ contiguous sets $Y_1, \dots, Y_C$ such that each $Y_\beta$ is of minimal size, with at least $\sqrt{|P||Q|}$ translation slabs associated to its elements

7: &nbsp;&nbsp;&nbsp;&nbsp;For every $Y_\beta$ let $y_\beta^+$ be its last element

8: &nbsp;&nbsp;&nbsp;&nbsp;Let $Y_{\text{heavy}} = \{y_\beta^+ | \beta \le C\}$, and $Y_\beta \leftarrow Y_\beta \setminus \{y_\beta^+\}$ for every $\beta \le C$

9: &nbsp;&nbsp;&nbsp;&nbsp;Let $\tau$ be the element in $X \times Y_{\text{heavy}}$ where $\text{area}(P \cap (Q+\tau))$ is maximum, via Lemma 11

10: &nbsp;&nbsp;&nbsp;&nbsp;$A \leftarrow \text{area}(P \cap (Q + \tau))$

11: &nbsp;&nbsp;&nbsp;&nbsp;**for** $\beta = 1, \dots, C$ **do** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ outer loop

12: &nbsp;&nbsp;&nbsp;&nbsp;Let $y_1 \in Y_\beta$ be the first element in $Y_\beta$ and $Q = X \times \{y_1\}$

13: &nbsp;&nbsp;&nbsp;&nbsp;Compute $A_q, B_q, C_q$ and $D_q$ for every $q \in Q$, via Lemma 11

14: &nbsp;&nbsp;&nbsp;&nbsp;Let $\mathcal{R}_\beta$ be the translation slabs associated to elements in $Y_\beta$

15: &nbsp;&nbsp;&nbsp;&nbsp;Compute the arrangement $\mathcal{A}_\beta$ of $\{[l, r) | [l, r) \times [b, \infty) \in \mathcal{R}_\beta\}$

16: &nbsp;&nbsp;&nbsp;&nbsp;Partition $X$ into contiguous sets $X_1, \dots, X_{C'}$ according to $\mathcal{A}_\beta$

17: &nbsp;&nbsp;&nbsp;&nbsp;**for** $\alpha = 1, \dots, C'$ **do** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ inner loop

18: &nbsp;&nbsp;&nbsp;&nbsp;Let $\mathcal{R}_{\alpha, \beta}$ be the set of translation slabs $[l, r) \times [b, \infty)$ in $\mathcal{R}_\beta$ with $X_\alpha \subset [l, r)$

19: &nbsp;&nbsp;&nbsp;&nbsp;**for** $y_j \in Y_\beta$ **do** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ transform $Y_\beta$ to $V \subset \mathbb{R}^3$

20: &nbsp;&nbsp;&nbsp;&nbsp;Let $\mathcal{R}_{\alpha, \beta, j}$ be the slabs $[l, r) \times [b, \infty)$ in $\mathcal{R}_{\alpha, \beta}$ with $y_1 < b \le y_j$

21: &nbsp;&nbsp;&nbsp;&nbsp;Let $v_j = ((y_j - y_1), \sum_{R \in \mathcal{R}_{\alpha, \beta, j}} (B_R + D_R y_j), \sum_{R \in \mathcal{R}_{\alpha, \beta, j}} (A_R + C_R y_j)^T)$

22: &nbsp;&nbsp;&nbsp;&nbsp;Let $V = \{v_j | y_j \in Y_\beta\}$

23: &nbsp;&nbsp;&nbsp;&nbsp;**for** $x_i \in X_\alpha$ **do** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Query $V$ instead of $Y_\beta$

24: &nbsp;&nbsp;&nbsp;&nbsp;Compute $M = \max_{v_j \in V} \langle v_j, (C_q + D_q x_i, x_i, 1)^T \rangle$ realized by $v_{j^*} \in V$

25: &nbsp;&nbsp;&nbsp;&nbsp;$A' = A_q + B_q x_i + C_q y_1 + D_q x_i y_1 + M$

26: &nbsp;&nbsp;&nbsp;&nbsp;**if** $A' > A$ **then** $A \leftarrow A'$, $\tau \leftarrow (x_i, y_{j^*})$

27: &nbsp;&nbsp;&nbsp;&nbsp;**Return** $\tau, A$
As the sets $Y_\beta$ partition $Y \setminus Y_{\text{heavy}}$, and for any fixed $Y_\beta$ the sets $X_\alpha$ partition $X$, it suffices to show that for any $\alpha, \beta$, and $x_i \in X_\alpha$ the value $A'$ computed in line 25 corresponds to $\max_{y_j \in Y_\beta}$ area$(P \cap (Q + (x_i, y_j)))$. For this, consider some iteration of the outer **for** loop in line 11 and fix some $\alpha \le C'$. Next, observe that $\mathcal{R}_{\alpha,\beta}$ is exactly the set of translation slabs $[l,r) \times [b, \infty)$ in $\mathcal{R}(P,Q)$ which has its lower boundary $b$ coincide with some $y_j \in Y_\beta$ and $X_\alpha \subset [l,r)$. In particular, this implies that for the first element $y_1$ in $Y_\beta$ and any $x_i \in X_\alpha$ and $y_j \in Y_\beta$ the set $\{R \in \mathcal{R}(P,Q) | (x_i, y_j) \in R\}$ decomposes into $\{R \in \mathcal{R}(P,Q) | (x_i, y_1) \in R\}$ and $\mathcal{R}_{\alpha,\beta,j} = \{[l,r) \times [b, \infty) \in \mathcal{R}_{\alpha,\beta} | y_1 < b \le y_j\}$. And thus for $q = (x_i, y_1) \in Q$ we have

$$
\begin{align*}
\text{area}(P \cap (Q + (x_i, y_j))) &= \sum_{R \in \mathcal{R}(P,Q)} 1[(x_i, y_j) \in R] (A_R + B_R x_i + C_R y_j + D_R x_i y_j) \\
&= \sum_{R \in \mathcal{R}(P,Q)} 1[q \in R] (A_R + B_R x_i + C_R y_j + D_R x_i y_j) + \sum_{R \in \mathcal{R}_{\alpha,\beta,j}} (A_R + B_R x_i + C_R y_j + D_R x_i y_j) \\
&= A_q + B_q x_i + C_q y_j + D_q x_i y_j + \sum_{R \in \mathcal{R}_{\alpha,\beta,j}} (A_R + B_R x_i + C_R y_j + D_R x_i y_j)
\end{align*}
$$

for the values $A_q, B_q, C_q$ and $D_q$ computed for $q$ in line 13 via Lemma 11. Finally as

$$
\begin{align*}
& \max_{y_j \in Y_\beta} (\text{area}(P \cap (Q + (x_i, y_j)))) \\
&= \max_{y_j \in Y_\beta} \left( A_q + B_q x_i + C_q y_j + D_q x_i y_j + \sum_{R \in \mathcal{R}_{\alpha, \beta, j}} (A_R + B_R x_i + C_R y_j + D_R x_i y_j) \right) \\
&= \max_{y_j \in Y_\beta} \left( A_q + B_q x + C_q y_1 + C_q (y_j - y_1) + D_q x y_1 + D_q x (y_j - y_1) \right. \\
& \qquad \left. + \sum_{R \in \mathcal{R}_{\alpha, \beta, j}} (A_R + B_R x_i + C_R y_j + D_R x_i y_j) \right) \\
&= A_q + B_q x_i + C_q y_1 + D_q x_i y_1 \\
& \qquad + \max_{y_j \in Y_\beta} \left( (C_q + D_q x_i)(y_j - y_1) + \left( \sum_{R \in \mathcal{R}_{\alpha, \beta, j}} (B_R + D_R y_j) \right) x_i + \sum_{R \in \mathcal{R}_{\alpha, \beta, j}} (A_R + C_R y_j) \right) \\
&= A_q + B_q x_i + C_q y_1 + D_q x_i y_1 + \max_{y_j \in Y_\beta} \left\langle \begin{pmatrix} y_j - y_1 \\ \sum_{R \in \mathcal{R}_{\alpha, \beta, j}} (B_R + D_R y_j) \\ \sum_{R \in \mathcal{R}_{\alpha, \beta, j}} (A_R + C_R y_j) \end{pmatrix}, \begin{pmatrix} C_q + D_q x_i \\ x_i \\ 1 \end{pmatrix} \right\rangle,
\end{align*}
$$

the computed value $A'$ in line 13 is exactly $\max_{y_j \in Y_\beta} (\text{area}(P \cap (Q + (x_i, y_j))))$. $\triangle$

<figure><img src="image_5.png" /></figure>

We remark that the sole purpose of $Y_{\text{heavy}}$ is to guarantee that each $Y_\beta$ has at most $\sqrt{nm}$ translation slabs associated to it, and in turn the arrangement $A_\beta$ consists of at most $O(\sqrt{nm})$ contiguous subsets of $X$. This is important, as we transform $Y_\beta$ into a different set $V$ for each contiguous subset in $A_\beta$. We note that by construction any $y \in Y$ that has at least $\sqrt{nm}$ translation slabs associated to it will end up in $Y_{\text{heavy}}$. As there are at most $O(nm)$ translation slabs, $Y_{\text{heavy}}$ cannot be too big, and hence $\text{area}(P \cap (Q + \tau)) = \max_{\tau' \in X \times Y_{\text{heavy}}} \text{area}(P \cap (Q + \tau'))$ can be computed efficiently via Lemma 11. In fact, as every $y \in Y$ has at least one translation slab associated to it (Lemma 5 and Corollary 6), $Y_{\text{heavy}}$ can be seen as just being a safe guard against inputs that are not in 'general position', where $|Y| \ll nm$. The exponent of $3/2$ is the result of balancing the sizes of $Y_\beta$ with the sizes of $X_\alpha$.
XX:12 On the Maximum Overlap of Two Polygons Under Translation

**Lemma 15.** Let P and Q be orthogonal polygons with n and m vertices respectively. The algorithm described in Algorithm 1 provided with P and Q has running time $O((nm)^{3/2} \log(nm))$.

**Proof.** First observe that Y in line 6 can be partitioned via a linear scan in $O(nm)$ time. Furthermore, observe that for any $\beta \le C$ the set $Y_{\beta} \setminus \{y_{\beta}^+\}$ has less than $\sqrt{nm}$ translation slabs associated to it, as otherwise $Y_{\beta}$ would not have been minimal. Hence after line 8 the set $Y_{\text{heavy}}$ and all sets $Y_{\beta}$ together partition Y, $|Y_{\text{heavy}}| \le O(\sqrt{nm})$, and each $Y_{\beta}$ has at most $\sqrt{nm}$ translation slabs associated to it. Note that $|Y_{\beta}| \le O(\sqrt{nm})$ as any $y \in Y$ has at least one translation slab associated to it (Lemma 5 and Corollary 6). By Lemma 11, line 9 and line 10 take a total of $O((nm)^{3/2} \log(nm))$ time.

Now consider one iteration of the outer **for** loop in line 11. Lines 12–15 take a total of $O(\sqrt{nm} \log(nm))$ time, by Lemma 11 together with the fact that $|R_{\beta}| \le \sqrt{nm}$. With $A_{\beta}$ at hand, computing the partition of X in line 16 takes $O(nm)$ time.

Now consider one iteration of the inner **for** loop in line 17. $R_{\alpha,\beta}$ can be computed in $O(|R_{\beta}|) = O(\sqrt{nm})$ time. Similarly, for every $y_j \in Y_{\beta}$ the values $\sum_{R \in R_{\alpha,\beta,j}} A_R$, $\sum_{R \in R_{\alpha,\beta,j}} B_R$, $\sum_{R \in R_{\alpha,\beta,j}} C_R$, and $\sum_{R \in R_{\alpha,\beta,j}} D_R$ and with it the set V can be computed in $O(\sqrt{nm})$ time via a linear scan of $Y_{\beta}$, as $R_{\alpha,\beta,j}$ and $R_{\alpha,\beta,j+1}$ differ by exactly all translation slabs in $R_{\alpha,\beta}$ associated to $y_{j+1}$. By Lemma 13, endowing the set V with a data structure allowing three-dimensional extreme-point queries can be done in time $O(\sqrt{nm} \log(nm))$. Finally, each iteration of the **for** loop in line 23 takes $O(\log(nm))$ time, computing $\max_{v_j \in V} \langle v_j, (C_q + D_q x_i, x_i, 1)^T \rangle$ via the computed data structure in $O(\log(|V|))$ time by Lemma 13. Thus each iteration of the inner **for** loop in line 17 takes $O(\sqrt{nm} \log(nm) + |X_{\alpha}| \log(nm))$ time. This implies that the iteration of the outer **for** loop in line 11 takes total time in

$$O\left( nm + \sqrt{nm} \log(nm) + \sum_{\alpha \le C'} (\sqrt{nm} \log(nm) + |X_{\alpha}| \log(nm)) \right) = O(nm \log(nm)).$$

Finally the total running time of the algorithm is bound by

$$O\left( (nm)^{3/2} \log(nm) + \sum_{\beta \le C} (nm \log(nm)) \right) = O\left( (nm)^{3/2} \log(nm) \right). \quad \blacksquare$$

**Theorem 1.** Let P and Q be orthogonal polygons with n and m vertices, respectively. There is an algorithm for computing the translation $\tau$ maximizing the overlap area($P \cap (Q + \tau)$) in time $O((nm)^{3/2} \log(nm))$.

**Proof.** This is an immediate consequence of Lemma 14 and Lemma 15. ▲

4 Lower Bounds

We now complement our algorithmic results by giving a lower bound. We reduce to the Polygon Overlap problem from a slightly more general form of 5-SUM, which we call the imbalanced 5-SUM, or (3, 2)-SUM:

**Problem 3** ((3, 2)-SUM). Given three sets of positive integers A, B, and C, of size n each, and two sets D, and E of size $m \le n$ each, is there $(a, b, c, d, e) \in A \times B \times C \times D \times E$ such that $a = b + c + d + e$?

**Lemma 16.** Assuming the k-SUM Hypothesis, then (3, 2)-SUM with sets of size n and $m \le n$ cannot be solved in $O((\max(n^2, nm^2))^{1-\epsilon})$ time for any $\epsilon > 0$.
**Proof.** First, observe that any 3-SUM instance can be transformed into a (3,2)-SUM instance with $m=1$, hence (3,2)-SUM cannot be solved in $O(n^{2-\epsilon})$ time.

Next, observe that any 5-SUM instance can be split into $\Theta((n/m)^2)$ (3,2)-SUM instances where the original 5-SUM instance has a solution if and only if one of the (3,2)-SUM instances has a solution. This is the case by splitting two sets of the 5-SUM instance into $\lfloor \frac{n}{m} \rfloor$ sets of size $m$ each, forming one (3,2)-SUM instance for every combination of these smaller sets. Hence, by the pidgeon hole principle, at least one (3,2)-SUM instance cannot be solved in $O(n^{3-\epsilon}/(n/m)^2) = O((nm^2)^{1-\epsilon})$ time concluding the proof. ◀

## 4.1 Construction

Let $A, B, C, D$ and $E$ constitute a (3,2)-SUM instance. We assume the sets to be sorted. We now construct two polygons $P$ and $Q$ with $O(n)$ and $O(m)$ vertices respectively, together with a value $\alpha$ such that deciding if $\max_{\tau \in \mathbb{R}^2} \text{area}(P \cap (Q + \tau)) \ge \alpha$ amounts to verifying that the (3,2)-SUM instance has a solution.

For the construction we fix two parameters. The first parameter $M$ we choose to be $100 \sum_{S \in \{A,B,C,D,E\}} \sum_{s \in S} S$. The parameter $M$ will serve as a trivial upper bound to any solution. The second parameter $\epsilon$ we choose to be $1/(100n^2)$, serving as a sufficiently small grid size on which we construct the polygons$^2$.

Observe that we can connect any set of $n$ pairwise disjoint polygons to form a single polygon via $O(n)$ polygons with measure 0. As such, we may describe the polygons $P$ and $Q$ as a union of disjoint polygons instead$^3$. Both $P$ and $Q$ consist of four gadgets each. We give the precise construction of the gadgets first, before giving intuition on the constructed instance. We conclude proving that computing the maximum overlap between these polygons amounts to solving (3,2)-SUM. For the construction of the gadgets (except for the anchor gadget) refer to Figure 2.

**Anchor gadget** Both $P$ and $Q$ have an anchor gadget, whose sole purpose is to restrict the set of translations which may attain the maximum. The anchor gadget $P_A$ of $P$ is a square with side length $M$ including the anchor gadget $Q_A$ of $Q$ being a square of side length 1 sufficiently far away from the origin. More precisely, the anchor gadget of $P$ is defined by the vertices $(0, 100M)$, $(0, 101M+1)$, $(M, 101M+1)$ and $(M, 100M)$, and the anchor gadget of $Q$ is defined by the vertices $(0, 100M)$, $(0, 100M+1)$, $(1, 100M+1)$ and $(1, 100M)$. Observe in particular that the anchor gadgets lie on the grid with side length $\epsilon$.

**Origin** Unlike the anchor gadget, which is far away from the origin, all other pieces of non-zero measure of $P$ and $Q$ are contained in $[-2M, 3M] \times [-2M, 3M]$, as we will see later. The rectangle $[0, M] \times [0, M]$ is part of $P$ and serves as a root polygon to which its other gadgets are attached.

**$x$-comb gadget** For the $i^{th}$ element $b_i \in B$ add the rectangle $P_x^i = [b_i + (3i+1)\epsilon, b_i + (3i+2)\epsilon] \times [-2M, 0]$ to $P$, which we refer to as the $i^{th}$ $x$-prong of $P$. For the $k^{th}$ element $d_k \in D$

<footnote n="2">2 Note that our choices of both $M$ and $\epsilon$ are quite conservative. We believe the construction works with $M = \Theta(\max_{S \in \{A,B,C,D,E\}} \max_{s \in S} S)$ and $\epsilon = \Theta(1/n)$ as well.</footnote>

<footnote n="3">3 We remark that we use measure 0 connections for ease of exposition. The same construction also works with connecting pieces with non-zero measure, as long as the total measure $\mu$ of all connecting pieces is sufficiently small, i.e., in particular $\mu \ll \epsilon^2$.</footnote>
XX:14 On the Maximum Overlap of Two Polygons Under Translation

<figure><img src="image_6.png" /><figcaption>■ **Figure 2** Construction of the polygons P and Q such that maximizing area($P \cap (Q + \tau)$) amounts to solving a (3, 2)-SUM instance. The anchor gadgets of P and Q are not shown.</figcaption></figure>

we add the square $Q_x^k[-d_k, -d_k + \varepsilon] \times [-2M, -2M + \varepsilon]$ to $Q$, which we refer to as the $k^{th}$ $x$-prong of $Q$.

**y-comb gadget** For the $j^{th}$ element $c_j \in C$ add the rectangle $P_y^j = [M, 3M] \times [c_j + (3j + 1)\varepsilon, c_j + (3j + 2)\varepsilon]$ to $P$, which we refer to as the $j^{th}$ $y$-prong of $P$. For the $l^{th}$ element $e_l \in E$ we add the square $Q_y^l = [2M - \varepsilon, 2M] \times [-e_l, -e_l + \varepsilon]$ to $Q$, to which we refer as the $l^{th}$ $y$-prong of $Q$.

**sum gadget** For the $h^{th}$ element $a_h \in A$ let $P_d^h$ be the polygon resulting from restricting the set $\{(x, y) \in \mathbb{R}^2 | a_h \le x + y \le a_h + (10n + 2)\varepsilon\}$ to $([-2M, M] \times [0, 3M]) \setminus ([0, M] \times [0, M])$, and add it to $P$. We call the polygon corresponding to $a_h$ the $h^{th}$ diagonal prong of $P$. Lastly add the single square $Q_v = [-2M, -2M + \varepsilon] \times [2M, 2M + \varepsilon]$ to $Q$, called the verifier of $Q$.

**Intuition** The role of the anchor gadgets is to restrict the set of translations $\tau$ such that area($P \cap (Q + \tau)$) > 1 to $[0, M] \times [0, M]$. This is achieved since outside the anchor gadget of $Q$ (which has measure exactly 1), $Q$ has a total measure of $(2n + 1)\varepsilon \ll 1$. Hence, any translation that attains an overlap of more than 1 must place the anchor gadget of $Q$ within the anchor gadget of $P$ and move at least one prong of $Q$ inside $P$.

The role of the $x$-prongs is slightly more involved: By construction of the anchor gadgets, any $x$-prong of $Q$ may only be translated to intersect an $x$-prong of $P$. By the $(3i)\varepsilon$-shifts applied to the $x$-prongs of $P$, at most one $x$-prong of $Q$ can ever intersect any $x$-prong of $P$. Thus, the area attained from intersections between $x$-prongs of $Q$ and $P$ is in $[0, \varepsilon^2]$, and in particular non-zero if and only if the $x$-coordinate of the translation is (approximately) $b_i + d_k$ for some $j$ and $k$. The role of the $y$-prongs is analogous and guarantees that at the area of the intersection between the $y$-prongs of $Q$ and $P$ is in $[0, \varepsilon^2]$ and only non-zero if the $y$-coordinate of the translation is (approximately) $c_j + e_l$.

Similarly to the $x$-prongs and the $y$-prongs, the verifier of $Q$ can intersect $P$ only in its diagonal prongs. In particular, if the verifier intersects the $h^{th}$ diagonal prong, then the sum of the $x$- and $y$-coordinates of the translation moving the verifier into the prong is
<figure><img src="image_7.png" /><figcaption>Figure 3 Illustration of the correctness of the 5-SUM lower bound with the $\varepsilon$-shifts for a given translation $(d_k + b_i + (3i+1)\varepsilon, e_\ell + c_j + (3j+1)\varepsilon)$. The highlighted areas starting from right to left in a clock-wise order correspond (i) for no $\ell' \neq \ell$ can the $\ell^{th}$ y-prong of $Q$ align with a y-prong of $P$ if $\varepsilon \ll 1/n$, (ii) the $\ell^{th}$ y-prong of $Q$ aligns with the $j^{th}$ y-prong of $P$, (iii) the $k^{th}$ x-prong of $Q$ aligns with the $i^{th}$ x-prong of $P$, (iv) for no $k' \neq k$ can the $k^{th}$ x-prong of $Q$ align with a y-prong of $P$ if $\varepsilon \ll 1/n$, and (v) if there is an $a_h$ with $a_h = b_i + c_j + d_k + e_\ell$, then the verifier of $Q$ lies in the $h^{th}$ diagonal prong of $P$. Otherwise, if $\varepsilon \ll 1/n$, then the diagonal prong of $Q$ lies outside of $P$.</figcaption></figure>

(approximately) equal to $a_h$. Hence in total, we can (approximately) verify that there is a ($a_h, b_i, c_j, d_k, e_\ell \in A \times B \times C \times D \times E$ with $a_h = b_i+c_j+d_k+e_\ell$ by checking if the maximum overlap is at least (or rather exactly) $1 + 3\varepsilon^2$ and strictly less than $1 + 3\varepsilon^2$ otherwise.

## 4.2 Correctness

We proceed as described above, first restricting the translations attaining an area of overlap of at least 1 to translations in $[0, M] \times [0, M]$, and then further restricting the translations via the careful positioning of the prongs.

**Lemma 17.** Let $P$ and $Q$ be polygons as constructed previously. Any translation $\tau$ such that $\text{area}(P \cap (Q + \tau)) > 1$ must be in $[-1, M+1] \times [-1, M+1]$.

**Proof.** By construction of $Q$, $\text{area}(P \cap (Q + \tau)) > 1$ only if $\text{area}(P \cap (Q_A + \tau)) > 0$ and $\text{area}(P \cap ((Q \setminus Q_A) + \tau)) > 0$. The first is only possible if $Q_A$ intersects either $P_A$ or $[-2M, 3M] \times [-2M, 3M]$, i.e., either $\tau \in ([-1, M+1] \times [-1, M+1])$ or $([-102M-1, -97M] \times [-2M-1, 3M])$. However, in the second case $(Q \setminus Q_A) + \tau$ lies below the line $y = -50M$. As $P$ lies completely above the line $y = -2M$, $\tau \in ([-1, M+1] \times [-1, M+1])$. ◀

We now concern ourselves with all other gadgets and their interactions. For the rest of this section, refer to Figure 3.

**Lemma 18.** Let $\tau \in [-1, M+1] \times [-1, M+1]$. Then

(i) $Q_v + \tau$ can only intersect diagonal prongs of $P$,

(ii) Any $Q_x^k + \tau$ can only intersect x-prongs of $P$, and
XX:16 On the Maximum Overlap of Two Polygons Under Translation

(iii) Any $Q_y^\ell + \tau$ can only intersect $y$-prongs of $P$.

**Proof.** For (i) observe that diagonal prongs are the only pieces of $P$ contained in $(-\infty, 0] \times \mathbb{R}$.
Now, for any $\tau \in [-1, M+1] \times [-1, M+1]$ it holds that $Q_v + \tau \in [-2M-1, -M+\varepsilon+1] \times [2M-1, 3M+\varepsilon+1]$ and hence $Q_v + \tau \subset (-\infty, 0] \times \mathbb{R}$.

For (ii) similarly observe that the only pieces of $P$ contained in $\mathbb{R} \times (-\infty, 0]$ are the $x$-prongs of $P$. Further, all $Q_x^k$ lie in $\mathbb{R} \times [-2M, -2M+\varepsilon]$. Hence $Q_x^k + \tau$ lies in $\mathbb{R} \times [-2M, -M+\varepsilon+1]$ and thus can only intersect $x$-prongs of $P$.

Lastly, for (iii) observe that the only pieces of $P$ contained in $[M+1, \infty) \times \mathbb{R}$ are the $y$-prongs of $P$. As before, $Q_x^\ell$ lies in $[2M-\varepsilon, 2M] \times \mathbb{R}$ and thus $Q_x^\ell + \tau$ lies in $[2M-\varepsilon-1, 3M+1] \times \mathbb{R}$ and so can only intersect the $y$-prongs of $P$, concluding the proof. ◀

**Lemma 19.** Let $\tau = (\tau_x, \tau_y) \in [-1, M+1] \times [-1, M+1]$. Then

(i) if area$(P \cap (Q_v + \tau)) > 0$, then $\exists a_h \in A$ such that $\tau_x + \tau_y \in [a_h - 2\varepsilon, a_h + (10n+2)\varepsilon]$,

(ii) if area$(P \cap (Q_x^k + \tau)) > 0$, then $\exists b_i \in B$ such that $\tau_x \in [d_k + b_i + 3i\varepsilon, d_k + b_i + (3i+2)\varepsilon]$, and

(iii) if area$(P \cap (Q_y^\ell + \tau))$, then $\exists c_j \in C$ such that $\tau_y \in [e_\ell + c_j + 3j\varepsilon, e_\ell + c_j + (3j+2)\varepsilon]$.

**Proof.** For (i) observe that by Lemma 18 $Q_v + \tau$ may only intersect diagonal prongs of $P$. As the $h^{\text{th}}$ diagonal prong is defined by (the restriction of) the set $\{(x, y) \in \mathbb{R}^2 | a_h \le x + y \le a_h + (10n+2)\varepsilon\}$, and $Q_v + \tau$ is a square with side length $\varepsilon$ with its lower left corner at $(-2M + \tau_x, 2M + \tau_y)$ the claim follows.

Similarly, for (ii), by Lemma 18 $Q_x^k + \tau$ may only intersect the $x$-prongs of $P$. As the $i^{\text{th}}$ $x$-prong of $P$ is defined by the (restriction of) the set $\{(x, y) \in \mathbb{R}^2 | b_i + (3i+1)\varepsilon \le x \le b_i + (3i+2)\varepsilon\}$ and $Q_x^k + \tau$ is a square with side length $\varepsilon$ with its lower left corner at $(-d_k + \tau_x, -2M + \tau_y)$, the claim follows.

The proof for (iii) is analogous to the proof of (ii). ◀

**Lemma 20.** Let $\tau = (\tau_x, \tau_y) \in [-1, M+1] \times [-1, M+1]$. Then

(i) area$(P \cap (Q_v + \tau)) \le \varepsilon^2$,

(ii) area$(P \cap (\bigcup_k Q_x^k + \tau)) \le \varepsilon^2$, and

(iii) area$(P \cap (\bigcup_\ell Q_y^\ell + \tau)) \le \varepsilon^2$.

**Proof.** For (i) observe that area$(Q_v) \le \varepsilon^2$.

For (ii), suppose that area$(P \cap (\bigcup_k Q_x^k + \tau)) > \varepsilon^2$ for the sake of contradiction. Hence, by Lemma 19, there are two indices $l \ne l'$ such that there is $i, i'$ such that $\tau_x \in [d_k + b_i + 3i\varepsilon, d_k + b_i + (3i+2)\varepsilon]$ and $\tau_x \in [d_{k'} + b_{i'} + 3i'\varepsilon, d_{k'} + b_{i'} + (3i'+2)\varepsilon]$. Then for both $i$ and $i'$ it holds that $3i\varepsilon, (3i+2)\varepsilon, 3i'\varepsilon$, and $(3i'+2)\varepsilon$ are in $[0, 5n\varepsilon] = [0, 1/(20n)) \subset [0, 1)$. Further, both $d_k + b_i$ and $d_{k'} + b_{i'}$ are integers. Thus, $\tau_x \in \mathbb{N} + [3i\varepsilon, (3i+2)\varepsilon]$ and $\tau_x \in \mathbb{N} + [3i'\varepsilon, (3i'+2)\varepsilon]$. As both $[3i\varepsilon, (3i+2)\varepsilon]$ and $[3i'\varepsilon, (3i'+2)\varepsilon]$ are in $[0, 1)$, this is only possible if $[3i\varepsilon, (3i+2)\varepsilon]$ and $[3i'\varepsilon, (3i'+2)\varepsilon]$ intersect. As $i$ and $i'$ are also integers, $i = i'$. But as $\bigcup_k Q_x^k + \tau \subset \mathbb{R} \times [-2M + \tau_y, 2M + \varepsilon + \tau_y]$ and $P_x^i \subset [b_i + (3i+1)\varepsilon, b_i + (3i+2)\varepsilon] \times \mathbb{R}$, in particular

$$ \text{area}(P \cap (\bigcup_k Q_x^k + \tau)) \le \text{area}(P_x^i \cap (\bigcup_k Q_x^k + \tau)) \le \varepsilon^2, $$

concluding the proof for (ii). An analogous argument proves (iii). ◀

**Lemma 21.** Let $P$ and $Q$ be as constructed. The underlying (3, 2)-SUM instance has a solution if and only if there is a translation $\tau$ such that area$(P \cap (Q + \tau)) \ge 1 + 3\varepsilon^2$.
**Proof.** First assume there is $(a_h, b_i, c_j, d_k, e_\ell) \in A \times B \times C \times D \times E$ such that $a_h = b_i + c_j + d_k + e_\ell$. Then let $\tau^* = (d_k + b_i + (3i+1)\varepsilon, e_\ell + c_j + (3j+1)\varepsilon)$. Clearly $\tau^* \in [0, M]$. Observe that area$(P_x^i \cap (Q_x^k + \tau^*)) = \varepsilon^2$, area$(P_y^j \cap (Q_y^\ell + \tau^*)) = \varepsilon^2$, area$(P_d^h \cap (Q_v + \tau^*)) = \varepsilon^2$, and area$(P_A \cap (Q_A + \tau^*)) = 1$. Hence, by Lemma 20

$$ \text{area}(P \cap (Q + \tau^*)) = 1 + 3\varepsilon^2. $$

Now let area$(P \cap (Q + \tau)) \ge 1 + 3\varepsilon^2$ for some $\tau$. Then Lemma 17 implies that $\tau \in [-1, M] \times [-1, M]$. But then Lemma 20, the pidgeon hole principle, and the fact that area$(Q_A) = 1$ imply that area$(P \cap (Q_v + \tau)) = \varepsilon^2$, area$(P \cap (\bigcup_k Q_x^k + \tau)) = \varepsilon^2$, and area$(P \cap (\bigcup_\ell Q_y^\ell + \tau)) = \varepsilon^2$. But then Lemma 19 implies that there is $(a_h, b_i, c_j, d_k, e_\ell) \in A \times B \times C \times D \times E$ with

1. $\tau_x \in [d_k + b_i + 3i\varepsilon, d_k + b_i + (3i + 2)\varepsilon]$,

2. $\tau_y \in [e_\ell + c_j + 3j\varepsilon, e_\ell + c_j + (3j + 2)\varepsilon]$, and

3. $\tau_x + \tau_y \in [a_h - 2\varepsilon, a_h + (10n + 2)\varepsilon]$.

This in turn implies that the interval

$$ [d_k + b_i + e_\ell + c_j + 3(k + j)\varepsilon, d_k + b_i + e_\ell + c_j + (3(k + j) + 4)\varepsilon] $$

intersects $[a_h - 2\varepsilon, a_h + (10n + 2)\varepsilon]$. This implies in particular that

$$ d_k + b_i + e_\ell + c_j \in [a_h - 2\varepsilon + 3(k + j)\varepsilon, a_h + (10n + 2)\varepsilon + (3(k + j) + 4)\varepsilon] \\ \subset [a_h - 2\varepsilon, a_h + (25n)\varepsilon] = [a_h - 2\varepsilon, a_h + 1/(4n)]. $$

As both $2\varepsilon$ and $1/(4n)$ is less than 1, and $d_k + b_i + e_\ell + c_j$ and $a_h$ are integers, in particular $a_h = d_k + b_i + e_\ell + c_j$ concluding the proof. ◀

**► Theorem 3.** Let P and Q be polygons with n and m vertices, respectively, where $m \le n$ and $\delta \in \mathbb{R}^+$. Assume that all edges of P and Q are either horizontal, vertical or parallel to the diagonal. Assuming the k-SUM hypothesis, deciding whether there is a translation $\tau$ such that area$(P \cap (Q + \tau)) > \delta$ cannot be solved in $O((\max(n^2, nm^2))^{1-\varepsilon})$ time for any $\varepsilon > 0$.

**Proof.** This is an immediate consequence of Lemma 21 and Lemma 16 together with the fact that any coordinate in P and Q as constructed for Lemma 21 is polynomial in the underlying (3, 2)-SUM instance. ◀

## 4.3 Extensions to related problems

We remark that for $m = 1$, a minor modification of our construction implies similar bounds for the polygon containment problem. The minor modifications consist of the following: We remove the anchor gadget $P_A$ for P and place the anchor gadget $Q_A$ at $[0, 1] \times [0, 1]$. This similarly restricts translations to $[0, M] \times [0, M]$, as otherwise $Q_A$ is not contained in the origin polygon of P. We consider the 3-SUM instance as a (3, 2)-SUM instance with $D = E = \{0\}$. Note that this modified version of P does not require any connecting pieces. For Q, the connecting pieces that connect the unique x- and y-prongs of Q to the origin are straight lines. Hence, they are contained in any $P_x^i$ and $P_y^j$ if the corresponding prong of Q is contained in $P_x^i$ and $P_y^j$ respectively. Lastly, the connecting piece for $Q_v$ is a diagonal line from $Q_v$ to 0, such that it is contained in the diagonal prong of P if it contains $Q_v$.

Thus for the problem of POLYGONCONTAINMENT we obtain a similar lower bound to the presented lower bound for the maximum overlap problem.

**► Problem 4 (POLYGONCONTAINMENT).** Let P and Q be two polygons in the plane with complexities n and m respectively. Is there a translation of Q such that it is contained in P?
XX:18 On the Maximum Overlap of Two Polygons Under Translation

**► Theorem 4.** Let P and Q be polygons with $n$ and $O(1)$ vertices, respectively. Assume that all edges of P and Q are either horizontal, vertical or parallel to the diagonal. Assuming the 3-SUM hypothesis, deciding whether there is a translation for Q such that Q is contained in P cannot be solved in $O(n^{2-\epsilon})$ time for any $\epsilon > 0$.

We believe that our reduction extends to higher dimensions encoding imbalanced $(2d+1)$-SUM instances as POLYTOPEMAXOVERLAP instances in $d$ dimensions where instead of polygons we want to maximize the measure of the overlap of two $d$-dimensional polytopes. Similarly, it encodes $(d+1)$-SUM instances as POLYTOPECONTAINMENT instances in $d$ dimensions, where the goal is to translate a $d$-dimensional polytope such that it is contained in another $d$-dimensional polytope. Assuming the $k$-SUM hypothesis, for POLYTOPECONTAINMENT in $d$ dimensions this reduction yields a lower bound of $O(n^{\lceil(d+1)/2\rceil-\epsilon})$, while for POLYTOPEMAXOVERLAP this reduction yields a lower bound of $O(\max(n^{\lceil(d+1)/2\rceil}, nm^d)^{1-\epsilon})$.

5 Open Problems

We leave multiple intriguing open problems for future work:

- It remains open what the optimal running time is for polygon containment and overlap on simple polygons when $m \in \omega(\text{polylog}(n))$.

- Surprisingly, we still do not know whether polygon overlap is harder than polygon containment for any class of polygons or whether these problems have essentially the same algorithmic complexity.

- To tackle the above problem, it would be interesting to resolve whether our algorithm for orthogonal polygons can be improved or show that it is tight with a lower bound for orthogonal polygons.

References

1 Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, *Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I*, volume 7965 of *Lecture Notes in Computer Science*, pages 1-12. Springer, 2013. doi:10.1007/978-3-642-39206-1_1.

2 Francis Avnaim and Jean-Daniel Boissonnat. Polygon placement under translation and rotation. *RAIRO Theor. Informatics Appl.*, 23(1):5-28, 1989. URL: https://doi.org/10.1051/ita/1989230100051, doi:10.1051/ITA/1989230100051.

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

4 Timothy M. Chan and Isaac M. Hair. Convex polygon containment: Improving quadratic to near linear time. In Wolfgang Mulzer and Jeff M. Phillips, editors, *40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece*, volume 293 of *LIPIcs*, pages 34:1-34:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. URL: https://doi.org/10.4230/LIPIcs.SoCG.2024.34, doi:10.4230/LIPICS.SOCG.2024.34.

5 Timothy M. Chan and Isaac M. Hair. A linear time algorithm for the maximum overlap of two convex polygons under translation. In Oswin Aichholzer and Haitao Wang, editors, *41st International Symposium on Computational Geometry, SoCG 2025, June 23-27, 2025, Kanazawa, Japan*, volume 332 of *LIPIcs*, pages 31:1-31:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. URL: https://doi.org/10.4230/LIPIcs.SoCG.2025.31, doi:10.4230/LIPICS.SOCG.2025.31.
6 Bernard Chazelle. The polygon containment problem. In F.P. Preparata, editor, *Advances in Computing Research*, volume 1, pages 1-33. JAI Press, 1983.

7 Siu-Wing Cheng and Chi-Kit Lam. Shape matching under rigid motion. *Comput. Geom.*, 46(6):591-603, 2013. URL: https://doi.org/10.1016/j.comgeo.2013.01.002, doi: 10.1016/J.COMGEO.2013.01.002.

8 Otfried Cheong, Alon Efrat, and Sariel Har-Peled. Finding a guard that sees most and a shop that sells most. *Discret. Comput. Geom.*, 37(4):545-563, 2007. URL: https://doi.org/10.1007/s00454-007-1328-5, doi:10.1007/S00454-007-1328-5.

9 Mark de Berg, Otfried Cheong, Olivier Devillers, Marc J. van Kreveld, and Monique Teillaud. Computing the maximum overlap of two convex polygons under translations. *Theory Comput. Syst.*, 31(5):613-628, 1998. doi:10.1007/PL00005845.

10 David P. Dobkin and David G. Kirkpatrick. A linear algorithm for determining the separation of convex polyhedra. *J. Algorithms*, 6(3):381-392, 1985. doi:10.1016/0196-6774(85)90007-0.

11 David P. Dobkin and David G. Kirkpatrick. Determining the separation of preprocessed polyhedra - A unified approach. In Mike Paterson, editor, *Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings*, volume 443 of Lecture Notes in Computer Science, pages 400-413. Springer, 1990. URL: https://doi.org/10.1007/BFb0032047, doi:10.1007/BFb0032047.

12 Anka Gajentaan and Mark H Overmars. On a class of o(n2) problems in computational geometry. *Computational Geometry*, 5(3):165-185, 1995. URL: https://www.sciencedirect.com/science/article/pii/0925772195000222, doi:10.1016/0925-7721(95)00022-2.

13 Sariel Har-Peled and Subhro Roy. Approximating the maximum overlap of polygons under translation. *Algorithmica*, 78(1):147-165, 2017. URL: https://doi.org/10.1007/s00453-016-0152-9, doi:10.1007/S00453-016-0152-9.

14 Antonio Hernández-Barrera. Algorithms for deciding the containment of polygons. *Inf. Process. Lett.*, 59(5):261-265, 1996. doi:10.1016/0020-0190(99)60016-8.

15 Marvin Künnemann and André Nusser. *Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union*, pages 3181–3201. SIAM, 2022. doi:10.1137/1.9781611977073.124.

16 David M. Mount, Ruth Silverman, and Angela Y. Wu. On the area of overlap of translated polygons. *Comput. Vis. Image Underst.*, 64(1):53-61, 1996. URL: https://doi.org/10.1006/cviu.1996.0045, doi:10.1006/CVIU.1996.0045.

17 Joseph O'Rourke, Subhash Suri, and Csaba D Tóth. Polygons. In *Handbook of discrete and computational geometry*, pages 787–810. Chapman and Hall/CRC, 2017.