Demaine, Erik D.; Korman, Matias; Ku, Jason S.; Mitchell, Joseph S. B.; Otachi, Yota; van Renssen, André; Roeloffzen, Marcel; Uehara, Ryuhei; Uno, Yushi Symmetric assembly puzzles are hard, beyond a few pieces. (English) Zbl 1450.05009 Comput. Geom. 90, Article ID 101648, 10 p. (2020). 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. Cited in 2 Documents 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) Keywords:assembly puzzle; NP-complete; parameterized algorithms PDFBibTeX XMLCite \textit{E. D. Demaine} et al., Comput. Geom. 90, Article ID 101648, 10 p. (2020; Zbl 1450.05009) 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.