×

Symmetric assembly puzzles are hard, beyond a few pieces. (English) Zbl 1450.05009

Summary: We study the complexity of symmetric assembly puzzles: given a collection of simple polygons, can we translate, rotate, and possibly flip them so that their interior-disjoint union is line symmetric? On the negative side, we show that the problem is strongly NP-complete even if the pieces are all polyominos. On the positive side, we show that the problem can be solved in polynomial time if the number of pieces is a fixed constant.

MSC:

05B40 Combinatorial aspects of packing and covering
05B50 Polyominoes
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
52C15 Packing and covering in \(2\) dimensions (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Slocum, J., The Tangram Book: The Story of the Chinese Puzzle with Over 2000 Puzzle to Solve (2004), Sterling Publishing
[2] Fox-Epstein, E.; Katsumata, K.; Uehara, R., The convex configurations of “Sei Shonagon Chie no Ita,” tangram, and other silhouette puzzles with seven pieces, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 99, 6, 1084-1089 (2016)
[3] H. Yamamoto, Personal communication, 2014.
[4] N. Iwase, Symmetrix, in: 24th International Puzzle Party (IPP 24), IPP24 Committee, unpublished, 2005, p. 54.
[5] Demaine, E. D.; Demaine, M. L., Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity, Graphs Comb., 23, Supplement, 195-208 (2007) · Zbl 1123.05027
[6] Cayley, A., A theorem on trees, Quart. J. Math., 23, 376-378 (1889) · JFM 21.0687.01
[7] Wolter, J. D.; Woo, T. C.; Volz, R. A., Optimal algorithms for symmetry detection in two and three dimensions, Vis. Comput., 1, 1, 37-48 (1985) · Zbl 0617.68042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.