14 citations · 29 across the 20 of their papers we have counts for
25 papers
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 c…
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…
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…
When Can You Tile an Integer Rectangle with Integer Squares?
MIT CompGeom Group, Zachary Abel, Hugo A. Akitaya +3
This paper characterizes when an rectangle, where and are integers, can be tiled (exactly packed) by squares where each has an integer side length of at least…
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…
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…
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 pr…
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…
Finding Closed Quasigeodesics on Convex Polyhedra
Erik D. Demaine, Adam C. Hesterberg, Jason S. Ku
A closed quasigeodesic is a closed curve on the surface of a polyhedron with at most of surface on both sides at all points; such curves can be locally unfolded straigh…
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…
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 …
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…