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

Metadata only

Date

2022Type

- Conference Paper

ETH Bibliography

yes
Altmetrics

Abstract

We revisit a classical problem in computational geometry: Determine the largest copy of a simple polygon P that can be placed into the simple polygon Q. Despite significant effort studying a number of settings, known algorithms require high polynomial running times, even for the interesting case when either P or Q have constant size. (Barequet and Har-Peled, 2001) give a conditional lower bound of n2–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 n2–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 translatedinto Q requires time n2–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 -time algorithm for orthogonal polygons P, Q with p and q vertices, respectively. This matches the lower bounds up to an n1/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 n3–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. Show more

Publication status

publishedExternal links

Book title

Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Pages / Article No.

Publisher

SIAMEvent

Organisational unit

02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies
Notes

Presentation held on January 12, 2022More

Show all metadata
ETH Bibliography

yes
Altmetrics