research
∙
09/18/2023
2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs
The 2-colorable perfect matching problem asks whether a graph can be col...
share
research
∙
08/29/2023
When Can You Tile an Integer Rectangle with Integer Squares?
This paper characterizes when an m × n rectangle, where m and n are inte...
research
∙
06/01/2023
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
We extend the motion-planning-through-gadgets framework to several new s...
research
∙
06/01/2023
Complexity of Simple Folding of Mixed Orthogonal Crease Patterns
Continuing results from JCDCGGG 2016 and 2017, we solve several new case...
research
∙
04/03/2023
Every Author as First Author
We propose a new standard for writing author names on papers and in bibl...
research
∙
03/27/2023
Complexity of Reconfiguration in Surface Chemical Reaction Networks
We analyze the computational complexity of basic reconfiguration problem...
research
∙
02/02/2023
Complexity of Solo Chess with Unlimited Moves
We analyze Solo Chess puzzles, where the input is an n × n board contain...
research
∙
02/02/2023
This Game Is Not Going To Analyze Itself
We analyze the puzzle video game This Game Is Not Going To Load Itself, ...
research
∙
12/23/2022
Computational Complexity of Flattening Fixed-Angle Orthogonal Chains
Planar/flat configurations of fixed-angle chains and trees are well stud...
research
∙
11/26/2022
Lower Bounds on Retroactive Data Structures
We prove essentially optimal fine-grained lower bounds on the gap betwee...
research
∙
11/21/2022
Celeste is PSPACE-hard
We investigate the complexity of the platform video game Celeste. We pro...
research
∙
07/14/2022
PSPACE-Completeness of Reversible Deterministic Systems
We prove PSPACE-completeness of several reversible, fully deterministic ...
research
∙
06/08/2022
Reconfiguration of Non-crossing Spanning Trees
For a set P of n points in the plane in general position, a non-crossing...
research
∙
04/07/2022
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles
A foundational result in origami mathematics is Kawasaki and Justin's si...
research
∙
03/31/2022
The Legend of Zelda: The Complexity of Mechanics
We analyze some of the many game mechanics available to Link in the clas...
research
∙
02/02/2022
Orthogonal Fold Cut
We characterize the shapes that can be produced by "orthogonal fold ...
research
∙
01/28/2022
Unfolding Orthotubes with a Dual Hamiltonian Path
An orthotube consists of orthogonal boxes (e.g., unit cubes) glued face-...
research
∙
12/15/2021
ZHED is NP-complete
We prove that the 2017 puzzle game ZHED is NP-complete, even with just 1...
research
∙
11/14/2021
Area-Optimal Simple Polygonalizations: The CG Challenge 2019
We give an overview of theoretical and practical aspects of finding a si...
research
∙
10/27/2021
An Efficient Reversible Algorithm for Linear Regression
This paper presents an efficient reversible algorithm for linear regress...
research
∙
09/30/2021
Rectangular Spiral Galaxies are Still Hard
Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit sq...
research
∙
09/09/2021
Any Regular Polyhedron Can Transform to Another by O(1) Refoldings
We show that several classes of polyhedra are joined by a sequence of O(...
research
∙
06/29/2021
Yin-Yang Puzzles are NP-complete
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-pap...
research
∙
05/22/2021
Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases
We prove that any finite polyhedral manifold in 3D can be continuously f...
research
∙
05/18/2021
Snipperclips: Cutting Tools into Desired Polygons using Themselves
We study Snipperclips, a computer puzzle game whose objective is to crea...
research
∙
03/11/2021
Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
research
∙
01/16/2021
Strings-and-Coins and Nimstring are PSPACE-complete
We prove that Strings-and-Coins – the combinatorial two-player game gene...
research
∙
12/14/2020
Characterizing Universal Reconfigurability of Modular Pivoting Robots
We give both efficient algorithms and hardness results for reconfiguring...
research
∙
11/23/2020
Arithmetic Expression Construction
When can n given numbers be combined using arithmetic operators from a g...
research
∙
10/19/2020
Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard
We prove PSPACE-completeness of two classic types of Chess problems when...
research
∙
09/29/2020
Tetris is NP-hard even with O(1) rows or columns
We prove that the classic falling-block video game Tetris (both survival...
research
∙
08/03/2020
Finding Closed Quasigeodesics on Convex Polyhedra
A closed quasigeodesic is a closed loop on the surface of a polyhedron w...
research
∙
07/31/2020
New Results in Sona Drawing: Hardness and TSP Separation
Given a set of point sites, a sona drawing is a single closed curve, dis...
research
∙
07/28/2020
Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra
We present new examples of topologically convex edge-ununfoldable polyhe...
research
∙
07/17/2020
Escaping a Polygon
Suppose an "escaping" player moves continuously at maximum speed 1 in th...
research
∙
06/08/2020
PSPACE-completeness of Pulling Blocks to Reach a Goal
We prove PSPACE-completeness of all but one problem in a large space of ...
research
∙
06/01/2020
Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
A door gadget has two states and three tunnels that can be traversed by ...
research
∙
06/01/2020
Negative Instance for the Edge Patrolling Beacon Problem
Can an infinite-strength magnetic beacon always “catch” an iron ball, wh...
research
∙
05/07/2020
Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets
We analyze the computational complexity of motion planning through local...
research
∙
04/08/2020
Computing Convex Partitions for Point Sets in the Plane: The CG:SHOP Challenge 2020
We give an overview of the 2020 Computational Geometry Challenge, which ...
research
∙
03/22/2020
1 x 1 Rush Hour with Fixed Blocks is PSPACE-complete
Consider n^2-1 unit-square blocks in an n × n square board, where each b...
research
∙
03/18/2020
Tatamibari is NP-complete
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an ...
research
∙
02/10/2020
Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players
We analyze the computational complexity of several new variants of edge-...
research
∙
10/22/2019
Folding Polyominoes with Holes into a Cube
When can a polyomino piece of paper be folded into a unit cube? Prior wo...
research
∙
08/21/2019
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers
We present the first universal reconfiguration algorithm for transformin...
research
∙
08/21/2019
Existence and hardness of conveyor belts
An open problem of Manuel Abellanas asks whether every set of disjoint c...
research
∙
06/30/2019
Waiting is not easy but worth it: the online TSP on the line revisited
We consider the online traveling salesman problem on the real line (OLTS...
research
∙
05/01/2019
Reconfiguring Undirected Paths
We consider problems in which a simple path of fixed length, in an undir...
research
∙
03/08/2019
Belga B-trees
We revisit self-adjusting external memory tree data structures, which co...
research
∙
01/24/2019
