Publications (9)
Robot Development and Path Planning for Indoor Ultraviolet Light Disinfection
Jonathan Conroy, Christopher Thierauf, Parker Rule +5
Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many indoor settings as a result of COVID-19, but current robotic systems at…
Facet-Hamiltonicity
Hugo Akitaya, Jean Cardinal, Stefan Felsner +2
We consider facet-Hamiltonian cycles of polytopes, defined as cycles in their skeleton such that every facet is visited exactly once. These cycles can be understood as optimal watc…
Rigid Foldability is NP-Hard
Hugo Akitaya, Erik D. Demaine, Takashi Horiyama +3
In this paper, we show that deciding rigid foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from Partition, and that deciding rigid foldabil…
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 …
Input-Sensitive Reconfiguration of Sliding Cubes
Hugo Akitaya, Matias Korman, Frederick Stock
A configuration of unit-cube-shaped \textit{modules} (or \textit{robots}) is a lattice-aligned placement of the modules so that their union is face-connected. The reconfigu…
Complexity of Simple Folding of Mixed Orthogonal Crease Patterns
Hugo Akitaya, Josh Brunner, Erik D. Demaine +3
Continuing results from JCDCGGG 2016 and 2017, we solve several new cases of the simple foldability problem -- deciding which crease patterns can be folded flat by a sequence of (s…
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…
Undecidability of Tiling with a Tromino
ULB CompGeom Group, Zachary Abel, Hugo Akitaya +6
Given a periodic placement of copies of a tromino (either L or I), we prove co-RE-completeness (and hence undecidability) of deciding whether it can be completed to a plane tiling.…
Recognizing Weakly Simple Polygons
Hugo Akitaya, Greg Aloupis, Jeff Erickson +1
We present an -time algorithm that determines whether a given planar -gon is weakly simple. This improves upon an -time algorithm by Chang, Erickson, a…