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.

BibTeX

@Article{RectangularSpiralGalaxies_CGTA,
  AUTHOR        = {Erik D. Demaine and Maarten L\"offler and Christiane Schmidt},
  TITLE         = {Rectangular {Spiral} {Galaxies} are still hard},
  JOURNAL       = {Computational Geometry: Theory and Applications},
  journalurl    = {https://www.sciencedirect.com/journal/computational-geometry},
  VOLUME        = 110,
  PAGES         = {101949},
  YEAR          = 2023,

  doi           = {https://dx.doi.org/10.1016/J.COMGEO.2022.101949},
  dblp          = {https://dblp.org/rec/journals/comgeo/DemaineLS23},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1016/j.comgeo.2022.101949">ScienceDirect</A> and as <A HREF="https://arXiv.org/abs/2110.00058">arXiv:2110.00058</A>.},
  papers        = {SpiralGalaxies_MOVES2017},
  length        = {31 pages},
}

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 and as arXiv:2110.00058.

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)