31 citations · 157 across the 51 of their papers we have counts for
66 papers
Reconfiguration of Non-crossing Spanning Trees
Oswin Aichholzer, Brad Ballinger, Therese Biedl +7
For a set of points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pa…
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…
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…
Hardness of Token Swapping on Trees
Oswin Aichholzer, Erik D. Demaine, Matias Korman +6
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to us…
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…
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…