10 citations · 25 across the 28 of their papers we have counts for
32 papers · 1 filter
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…
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.…
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…
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…
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…
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…
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…
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…
Rock Climber Distance: Frogs versus Dogs
Hugo A. Akitaya, Leonie Ryvkin, Csaba D. Tóth
The classical measure of similarity between two polygonal chains in Euclidean space is the Fréchet distance, which corresponds to the coordinated motion of two mobile agents along…
The -Fréchet distance
Hugo A Akitaya, Maike Buchin, Leonie Ryvkin +1
We introduce a new distance measure for comparing polygonal chains: the -Fréchet distance. As the name implies, it is closely related to the well-studied Fréchet distance but de…
Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Hugo A. Akitaya, Matias Korman, Oliver Korten +3
Given a planar straight-line graph in , a \emph{circumscribing polygon} of is a simple polygon whose vertex set is , and every edge in is eit…
Infinite All-Layers Simple Foldability
Hugo A. Akitaya, Cordelia Avery, Joseph Bergeron +3
We study the problem of deciding whether a crease pattern can be folded by simple folds (folding along one line at a time) under the infinite all-layers model introduced by [Akitay…
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…
Distance Measures for Embedded Graphs
Hugo A. Akitaya, Maike Buchin, Bernhard Kilgus +2
We introduce new distance measures for comparing straight-line embedded graphs based on the Fréchet distance and the weak Fréchet distance. These graph distances are defined using…
How to Fit a Tree in a Box
Hugo A. Akitaya, Maarten Löffler, Irene Parada
We study compact straight-line embeddings of trees. We show that perfect binary trees can be embedded optimally: a tree with nodes can be drawn on a by grid…