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

Given two polygons of complexities n and m respectively, a fundamental problem in shape matching and geometric similarity is to compute their maximum area overlap under translation. For general simple polygons, the best-known algorithm runs in O((nm) 2 log(nm)) time [Mount, Silverman, Wu '96]. 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-ε ), where m ≤ 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-ε ) 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,. Furthermore, our lower bounds show conditional tightness (up to polylogarithmic factors) of the algorithms of [Avnaim, Boissonnat '89] and [Mount, Silverman, Wu '96] when m ∈ O(1).

Keywords and phrases polygon overlap, polygon containment, algorithm design, lower bound Digital Object Identifier 10.4230/LIPIcs...