Publications (24)
Pachinko
Hugo A. Akitaya, Erik D. Demaine, Martin L. Demaine +4
Inspired by the Japanese game Pachinko, we study simple (perfectly "inelastic" collisions) dynamics of a unit ball falling amidst point obstacles (pins) in the plane. A classic exa…
Deltahedral Domes over Equiangular Polygons
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +6
A polyiamond is a polygon composed of unit equilateral triangles, and a generalized deltahedron is a convex polyhedron whose every face is a convex polyiamond. We study a variant w…
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
Jeffrey Bosboom, Charlotte Chen, Lily Chung +12
We analyze the computational complexity of several new variants of edge-matching puzzles. First we analyze inequality (instead of equality) constraints between adjacent tiles, prov…
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +3
We prove that path puzzles with complete row and column information--or equivalently, 2D orthogonal discrete tomography with Hamiltonicity constraint--are strongly NP-complete, ASP…
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…
Folding Polyominoes into (Poly)Cubes
Oswin Aichholzer, Michael Biro, Erik D. Demaine +6
We study the problem of folding a polyomino into a polycube , allowing faces of to be covered multiple times. First, we define a variety of folding models according to w…
Negative Instance for the Edge Patrolling Beacon Problem
Zachary Abel, Hugo A. Akitaya, Erik D. Demaine +5
Can an infinite-strength magnetic beacon always ``catch'' an iron ball, when the beacon is a point required to be remain nonstrictly outside a polygon, and the ball is a point alwa…
Snipperclips: Cutting Tools into Desired Polygons using Themselves
Zachary Abel, Hugo Akitaya, Man-Kwun Chiu +7
We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e…
Arithmetic Expression Construction
Leo Alcock, Sualeh Asif, Jeffrey Bosboom +10
When can given numbers be combined using arithmetic operators from a given subset of to obtain a given target number? We study three variations of this p…
Improved Connectivity Condition for Byzantine Fault Tolerance
Adam Hesterberg, Andrea Lincoln, Jayson Lynch
Given a network in which some pairs of nodes can communicate freely, and some subsets of the nodes could be faulty and colluding to disrupt communication, when can messages reliabl…
Even Edge-Matching and Jigsaw Puzzles are Really Hard
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +3
We prove the computational intractability of rotating and placing square tiles into a array such that adjacent tiles are compatible--either equal edge colors, as i…
New Results in Sona Drawing: Hardness and TSP Separation
Man-Kwun Chiu, Erik D. Demaine, Jenny Diomidova +6
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its co…
Characterizing Universal Reconfigurability of Modular Pivoting Robots
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi +7
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we co…
Conflict-Free Coloring of Planar Graphs
Zachary Abel, Victor Alvarez, Aman Gour +5
A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vert…
Escaping a Polygon
Zachary Abel, Hugo Akitaya, Erik D. Demaine +4
Suppose an escaping player ("human") moves continuously at maximum speed in the interior of a region, while a pursuing player ("zombie") moves continuously at maximum speed …
Quasigeodesics on the Cube
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +10
A quasigeodesic is a curve on the surface of a convex polyhedron that has surface to each side at every point. In contrast, a geodesic has exactly to each side and so…
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…
Multidimensional Scaling: Approximation and Complexity
Erik Demaine, Adam Hesterberg, Frederic Koehler +2
Metric Multidimensional scaling (MDS) is a classical method for generating meaningful (non-linear) low-dimensional embeddings of high-dimensional data. MDS has a long history in th…
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
Zachary Abel, Jeffrey Bosboom, Michael Coulombe +7
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw…
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…
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Josh Brunner, Lily Chung, Erik D. Demaine +4
Consider unit-square blocks in an square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable -- a variat…
Upward Partitioned Book Embeddings
Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg +1
We analyze a directed variation of the book embedding problem when the page partition is prespecified and the nodes on the spine must be in topological order (upward book embedding…
Super Guarding and Dark Rays in Art Galleries
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +5
We explore an Art Gallery variant where each point of a polygon must be seen by k guards, and guards cannot see through other guards. Surprisingly, even covering convex polygons un…
Tetris is NP-hard even with rows or columns
Sualeh Asif, Michael Coulombe, Erik D. Demaine +4
We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open prob…