Zobrazeno 1 - 10
of 112
pro vyhledávání: '"Akitaya, Hugo"'
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 watchman routes that guard the facets of a polytope. We consider the exist
Externí odkaz:
http://arxiv.org/abs/2411.02172
Autor:
Akitaya, Hugo A., Biniaz, Ahmad, Demaine, Erik D., Kleist, Linda, Stock, Frederick, Tóth, Csaba D.
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 endpoint. A MinBST can be computed in $O(n\log n)$ time where $n$ is the n
Externí odkaz:
http://arxiv.org/abs/2409.11614
Autor:
MIT CompGeom Group, Akitaya, Hugo A., Demaine, Erik D., Hesterberg, Adam, Lubiw, Anna, Lynch, Jayson, O'Rourke, Joseph, Stock, Frederick, Tkadlec, Josef
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 where one face may be an exception. For a convex polygon P, if there is
Externí odkaz:
http://arxiv.org/abs/2408.04687
Autor:
MIT CompGeom Group, Akitaya, Hugo A., Demaine, Erik D., Hesterberg, Adam, Lubiw, Anna, Lynch, Jayson, O'Rourke, Joseph, Stock, Frederick
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 under this variant is not straightforward. For example, covering every p
Externí odkaz:
http://arxiv.org/abs/2404.04613
The free space diagram is a popular tool to compute the well-known Fr\'echet distance. As the Fr\'echet distance is used in many different fields, many variants have been established to cover the specific needs of these applications. Often, the quest
Externí odkaz:
http://arxiv.org/abs/2311.07573
Autor:
MIT CompGeom Group, Abel, Zachary, Akitaya, Hugo A., Demaine, Erik D., Hesterberg, Adam C., Lynch, Jayson
This paper characterizes when an $m \times n$ rectangle, where $m$ and $n$ are integers, can be tiled (exactly packed) by squares where each has an integer side length of at least 2. In particular, we prove that tiling is always possible when both $m
Externí odkaz:
http://arxiv.org/abs/2308.15317
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}$, called a district map, is a set of interior disjoint connected pol
Externí odkaz:
http://arxiv.org/abs/2307.00704
Autor:
Akitaya, Hugo, Brunner, Josh, Demaine, Erik D., Hendrickson, Dylan, Luo, Victor, Tockman, Andy
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 (some model of) simple folds. We give new efficient algorithms for mixed
Externí odkaz:
http://arxiv.org/abs/2306.00702
Autor:
Akitaya, Hugo A., Stock, Frederick
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 space requirements for a pivoting move and investigate the $\textit{recon
Externí odkaz:
http://arxiv.org/abs/2304.09990
We investigate the reconfiguration of $n$ blocks, or "tokens", in the square grid using "line pushes". A line push is performed from one of the four cardinal directions and pushes all tokens that are maximum in that direction to the opposite directio
Externí odkaz:
http://arxiv.org/abs/2202.12045