Paper by Erik D. Demaine
- Reference:
- Erik D. Demaine, Maarten Löffler, and Christiane Schmidt, “Rectangular Spiral Galaxies are still hard”, Computational Geometry: Theory and Applications, volume 110, 2023, pages 101949.
- Abstract:
-
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.
- Comments:
- This paper is also available from ScienceDirect.
- Length:
- The paper is 31 pages.
- Availability:
- The paper is available in PDF (1040k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- SpiralGalaxies_MOVES2017 (Spiral Galaxies Font)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.