4 citations · 18 across the 22 of their papers we have counts for
28 papers
Polyomino Nets Covering Three Different Boxes of Area 106 and Related Results
Erik D. Demaine, Jenny Diomidova, Nicole Jacobus +5
We present new results for polyomino nets that fold into 2 and 3 different cuboids through a computer search. The main result is the finding of 40 nets that fold into all three dif…
On the Computational Complexity of Generalized Common Shape Puzzles
Mutsunori Banbara, Shin-ichi Minato, Hirotaka Ono +1
In this study, we investigate the computational complexity of some variants of generalized puzzles. We are provided with two sets S_1 and S_2 of polyominoes. The first puzzle asks…
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains
Erik D. Demaine, Hiro Ito, Jayson Lynch +1
Planar/flat configurations of fixed-angle chains and trees are well studied in the context of polymer science, molecular biology, and puzzles. In this paper, we focus on a simple t…
Sorting Balls and Water: Equivalence and Computational Complexity
Takehiro Ito, Jun Kawahara, Shin-ichi Minato +7
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled…
Solving Rep-tile by Computers: Performance of Solvers and Analyses of Solutions
Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama +7
A rep-tile is a polygon that can be dissected into smaller copies (of the same size) of the original polygon. A polyomino is a polygon that is formed by joining one or more unit sq…
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings
Erik D. Demaine, Martin L. Demaine, Jenny Diomidova +3
We show that several classes of polyhedra are joined by a sequence of O(1) refolding steps, where each refolding step unfolds the current polyhedron (allowing cuts anywhere on the…
Computational Complexity of Jumping Block Puzzles
Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara
In combinatorial reconfiguration, the reconfiguration problems on a vertex subset (e.g., an independent set) are well investigated. In these problems, some tokens are placed on a s…
Efficient Folding Algorithms for Regular Polyhedra
Tonan Kamata, Akira Kadoguchi, Takashi Horiyama +1
We investigate the folding problem that asks if a polygon P can be folded to a polyhedron Q for given P and Q. Recently, an efficient algorithm for this problem has been developed…
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares
Hugo A. Akitaya, Erik D. Demaine, Matias Korman +6
A well-established theoretical model for modular robots in two dimensions are edge-connected configurations of square modules, which can reconfigure through so-called sliding moves…
Efficient Segment Folding is Hard
Takashi Horiyama, Fabian Klute, Matias Korman +3
We introduce a computational origami problem which we call the segment folding problem: given a set of line-segments in the plane the aim is to make creases along all segments…
Cyclic Shift Problems on Graphs
Kwon Kham Sai, Ryuhei Uehara, Giovanni Viglietta
We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished c…
Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots
Giuseppe A. Di Luna, Ryuhei Uehara, Giovanni Viglietta +1
A swarm of anonymous oblivious mobile robots, operating in deterministic Look-Compute-Move cycles, is confined within a circular track. All robots agree on the clockwise direction…
Reconfiguring Undirected Paths
Erik D. Demaine, David Eppstein, Adam Hesterberg +4
We consider problems in which a simple path of fixed length, in an undirected graph, is to be shifted from a start position to a goal position by moves that add an edge to either e…
Design Schemes for Fair Dice
Tomoko Taniguchi, Ryuhei Uehara
A cube is used as a fair die of 6 faces. However, there are many dice of different shapes on the market. To make them fair, most of them usually have some symmetric shapes. We here…
Shortest Reconfiguration Sequence for Sliding Tokens on Spiders
Duc A. Hoang, Amanj Khorramian, Ryuhei Uehara
Suppose that two independent sets and of a graph with are given, and a token is placed on each vertex in . The Sliding Token problem is t…
Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil +5
We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices ca…
Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs
Duc A. Hoang, Ryuhei Uehara
Given two independent sets of a graph , and imagine that a token (coin) is placed at each vertex of . The Sliding Token problem asks if one could transform to …
Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces
Erik D. Demaine, Matias Korman, Jason S. Ku +6
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…
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…
Shortest Reconfiguration of Sliding Tokens on a Caterpillar
Takeshi Yamada, Ryuhei Uehara
Suppose that we are given two independent sets I_b and I_r of a graph such that |I_b|=|I_r|, and imagine that a token is placed on each vertex in |I_b|. Then, the sliding token pro…
Computational Complexity of Competitive Diffusion on (Un)weighted Graphs
Takehiro Ito, Yota Otachi, Toshiki Saitoh +6
Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a nu…
Folding a Paper Strip to Minimize Thickness
Erik D. Demaine, David Eppstein, Adam Hesterberg +4
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mo…
Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
Zachary Abel, Erik D. Demaine, Martin L. Demaine +3
When can a plane graph with prescribed edge lengths and prescribed angles (from among \}) be folded flat to lie in an infinitesimally thin line, without c…
The Convex Configurations of "Sei Shonagon Chie no Ita" and Other Dissection Puzzles
Eli Fox-Epstein, Ryuhei Uehara
The tangram and Sei Shonagon Chie no Ita are popular dissection puzzles consisting of seven pieces. Each puzzle can be formed by identifying edges from sixteen identical right isos…