44 citations · 115 across the 13 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.CG2021
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union
Marvin Künnemann, André Nusser
We revisit the classical problem of determining the largest copy of a simple polygon that can be placed into a simple polygon . Despite significant effort, known algorithms…
cs.DS2021
Fine-Grained Completeness for Optimization in P
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for dec…