TY - JOUR
T1 - Rectangular Spiral Galaxies are Still Hard
AU - Demaine, Erik D.
AU - Löffler, Maarten
AU - Schmidt, Christiane
N1 - Funding Information:
We thank the anonymous referees for helpful comments. C. S. was partially supported by Jubileumsanslaget från Knut och Alice Wallenbergs Stiftelse .
Publisher Copyright:
© 2022 The Author(s)
PY - 2023/3
Y1 - 2023/3
N2 - Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit squares: given a set of points called centers, the goal is to partition the grid into polyominoes such that each polyomino contains exactly one center and is 180∘ rotationally symmetric about its center. We show that this puzzle is NP-complete, ASP-complete, and #P-complete even if (a) all solutions to the puzzle have rectangles for polyominoes; or (b) the polyominoes are required to be rectangles and all solutions to the puzzle have just 1×1, 1×3, and 3×1 rectangles. The proof for the latter variant also implies NP/ASP/#P-completeness of finding a noncrossing perfect matching in distance-2 grid graphs where edges connect vertices of Euclidean distance 2. Moreover, we prove NP-completeness of the design problem of minimizing the number of centers such that there exists a set of galaxies that exactly cover a given shape.
AB - Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit squares: given a set of points called centers, the goal is to partition the grid into polyominoes such that each polyomino contains exactly one center and is 180∘ rotationally symmetric about its center. We show that this puzzle is NP-complete, ASP-complete, and #P-complete even if (a) all solutions to the puzzle have rectangles for polyominoes; or (b) the polyominoes are required to be rectangles and all solutions to the puzzle have just 1×1, 1×3, and 3×1 rectangles. The proof for the latter variant also implies NP/ASP/#P-completeness of finding a noncrossing perfect matching in distance-2 grid graphs where edges connect vertices of Euclidean distance 2. Moreover, we prove NP-completeness of the design problem of minimizing the number of centers such that there exists a set of galaxies that exactly cover a given shape.
KW - NP-completeness
KW - Non-crossing matching
KW - Pencil-and-paper puzzle
KW - Spiral Galaxies
UR - http://www.scopus.com/inward/record.url?scp=85139857130&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2022.101949
DO - 10.1016/j.comgeo.2022.101949
M3 - Article
SN - 0925-7721
VL - 110
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
M1 - 101949
ER -