| 1. |
|
|
| 2. |
- Aichholzer, Oswin, et al.
(author)
-
Folding Polyominoes with Holes into a Cube
- 2021
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 93
-
Journal article (peer-reviewed)abstract
- When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.
|
|
| 3. |
- Demaine, Erik D., et al.
(author)
-
Rectangular Spiral Galaxies are still hard
- 2023
-
In: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 110
-
Journal article (peer-reviewed)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 degrees 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 x 1, 1 x 3, and 3 x 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.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
|
|
| 4. |
- Kostitsyna, Irina, et al.
(author)
-
Most vital segment barriers
- 2019
-
In: Workshop on Algorithms and Data Structures. - : Springer, Cham. ; , s. 495-509
-
Conference paper (peer-reviewed)
|
|
