2021/11/03 by Marvin Künnemann, Künnemann, Marvin, André Nusser +1 · 2 citations
Computer Science · Engineering · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2111.02544
openalex publication_date 2021/11/03 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
We revisit the classical problem of determining the largest copy of a simple polygon P that can be placed into a simple polygon Q. Despite significant effort, known algorithms require high polynomial running times. (Barequet and Har-Peled, 2001) give a 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 kSUM conjecture, proving natural hardness results that increase with each degree of freedom (scaling, x-translation, y-translation, rotation): (1) Finding the largest copy of P that can be x-translated into Q requires time n2-o(1) under the 3SUM conjecture. (2) Finding the largest copy of P that can be arbitrarily translated into Q requires time n2-o(1) under the 4SUM conjecture. (3) The above lower bounds are almost tight when one of the polygons is of constant size: we obtain an O((pq)2.5)-time algorithm for orthogonal polygons P,Q with p and q vertices, respectively. (4) Finding the largest copy of P that can be arbitrarily rotated and translated into Q requires time n3-o(1) under the 5SUM conjecture. We are not aware of any other such natural (degree of freedom + 1)-SUM hardness for a geometric optimization problem.