10 citations · 25 across the 28 of their papers we have counts for
40 papers
Overlapping Unfoldings of Cones and Convex Polyhedra
MIT CompGeom Group, Hugo A. Akitaya, Erik D. Demaine +4
Research on Dürer's problem focuses on edge unfoldings of convex polyhedra that avoid overlap. We invert the goal and find unfoldings that overlap at some point to any given thickn…
The Balanced Up-Down Walk
Hugo A. Akitaya, Sarah Cannon, Gregory Herschlag +3
Markov chains based on spanning trees have been hugely influential in algorithms for assessing fairness in political redistricting. The input graph represents the geographic buildi…
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.…
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…
Sliding Squares in Parallel
Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer +4
We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given square-shaped modules in a (labeled or unlabele…
Minimum Plane Bichromatic Spanning Trees
Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine +3
For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endp…
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…
Realizability of Free Spaces of Curves
Hugo A. Akitaya, Maike Buchin, Majid Mirzanezhad +2
The free space diagram is a popular tool to compute the well-known Fréchet distance. As the Fréchet distance is used in many different fields, many variants have been established t…
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…
Reconfiguration of Polygonal Subdivisions via Recombination
Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine +2
Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon $\mathcal{R…
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…
Reconfiguration of 3D Pivoting Modular Robots
Hugo A. Akitaya, Frederick Stock
We study a new model of 3-dimensional modular self-reconfigurable robots Rhombic Dodecahedral (RD). By extending results on the 2D analog of this model we characterize the free spa…
Pushing Blocks by Sweeping Lines
Hugo A. Akitaya, Maarten Löffler, Giovanni Viglietta
We investigate the reconfiguration of blocks, or "tokens", in the square grid using "line pushes". A line push is performed from one of the four cardinal directions and pushes…
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares
Hugo A. Akitaya, Erik D. Demaine, Matias Korman +6
A well-established theoretical model for modular robots in two dimensions are edge-connected configurations of square modules, which can reconfigure through so-called sliding moves…
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…
Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves
Hugo A. Akitaya, Frederik Brüning, Erin Chambers +1
We study subtrajectory clustering under the Fréchet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a g…
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…
Reconfiguration of Connected Graph Partitions via Recombination
Hugo A. Akitaya, Matias Korman, Oliver Korten +2
Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph . A partition of is \emph{connected…
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…
Face flips in origami tessellations
Hugo A. Akitaya, Vida Dujmovi, David Eppstein +3
Given a flat-foldable origami crease pattern (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment …
Folding Polyominoes with Holes into a Cube
Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung +9
When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present s…
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The Musketeers
Hugo A. Akitaya, Esther M. Arkin, Mirela Damian +8
We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precise…