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

We revisit a classical problem in computational geometry: Determine the largest copy of a simple polygon P that can be placed into the simple polygon Q. Despite significant effort studying a number of settings, known algorithms require high polynomial running times, even for the interesting case when either P or Q have constant size. (Barequet and Har-Peled, 2001) give a conditional lower bound of n 2-o(1) under the 3SUM conjecture when P and Q are (convex) polygons with Θ(n) vertices each. This leaves open whether we can establish (1) hardness beyond quadratic time and (2) any superlinear bound for constant-sized P or Q.

In this paper, we affirmatively answer these questions under the higher-order kSUM conjecture, proving natural hardness results that increase with each degree of freedom (scaling, x-translation, y-translation, rotation):

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

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

• The above lower bounds are almost tight when one of the polygons is of constant size:

Using an offline dynamic algorithm for maintaining the area of a union of rectangles due to Overmars and Yap, we obtain an Õ((pq) 2.5 )-time algorithm for orthogonal polygons P, Q with p and q vertices, respectively. This matches the lower bounds up to an n 1/2+o(1)factor when P, Q have O(1) and n vertices.

• (scaling, x-translation, y-translation, rotation:) Finally, finding the largest copy of P that can be arbitrarily rotated and translated into Q requires time n 3-o(1) under the 5SUM conjecture. As in our reductions, each degree of freedom determines one summand in a kSUM instance, these lower bounds appear likely to be best possible under kSUM. We are not aware of any other such natural (degree of freedom+1)-SUM hardness for a geometric optimization problem. Finally, we prove an additional tight OV hardness of the translations-only case.