BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Hugo A. Akitaya appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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 sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special \emph{simple} holes guarantee foldability.
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 always moving instantaneously and maximally toward the beacon subject to staying nonstrictly within the same polygon? Kouhestani and Rappaport [JCDCG 2017] gave an algorithm for determining whether a ball-capturing beacon strategy exists, while conjecturing that such a strategy always exists. We disprove this conjecture by constructing orthogonal and general-position polygons in which the ball and the beacon can never be united.
Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $μ:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $F$ of $G$ to create a new MV assignment $μ_F$ which equals $μ$ except for all creases $e$ bordering $F$, where we have $μ_F(e)=-μ(e)$. In this paper we explore the configuration space of face flips for a variety of crease patterns $G$ that are tilings of the plane, proving examples where $μ_F$ results in a MV assignment that is either never, sometimes, or always flat-foldable for various choices of $F$. We also consider the problem of finding, given two foldable MV assignments $μ_1$ and $μ_2$ of a given crease pattern $G$, a minimal sequence of face flips to turn $μ_1$ into $μ_2$. We find polynomial-time algorithms for this in the cases where $G$ is either a square grid or the Miura-ori, and show that this problem is NP-hard in the case where $G$ is the triangle lattice.
We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG $G=(V,E)$ in general position can be augmented to a 2-connected PSLG $(V,E\cup E^+)$ by adding new edges of total Euclidean length $\|E^+\|\leq 2\|E\|$, and this bound is the best possible. An optimal edge set $E^+$ can be computed in $O(|V|^4)$ time; however the problem becomes NP-hard when $G$ is disconnected. Further, there is a sequence of edge insertions and deletions that transforms a connected PSLG $G=(V,E)$ into a planar straight-line cycle $G'=(V,E')$ such that $\|E'\|\leq 2\|{\rm MST}(V)\|$, and the graph remains connected with edge length below $\|E\|+\|{\rm MST}(V)\|$ at all stages. These bounds are the best possible.
We study a problem proposed by Hurtado et al. (2016) motivated by sparse set visualization. Given $n$ points in the plane, each labeled with one or more primary colors, a \emph{colored spanning graph} (CSG) is a graph such that for each primary color, the vertices of that color induce a connected subgraph. The \textsc{Min-CSG} problem asks for the minimum sum of edge lengths in a colored spanning graph. We show that the problem is NP-hard for $k$ primary colors when $k\ge 3$ and provide a $(2-\frac{1}{3+2\varrho})$-approximation algorithm for $k=3$ that runs in polynomial time, where $\varrho$ is the Steiner ratio. Further, we give a $O(n)$ time algorithm in the special case that the input points are collinear and $k$ is constant.
Inspired by the Japanese game Pachinko, we study simple (perfectly "inelastic" collisions) dynamics of a unit ball falling amidst point obstacles (pins) in the plane. A classic example is that a checkerboard grid of pins produces the binomial distribution, but what probability distributions result from different pin placements? In the 50-50 model, where the pins form a subset of this grid, not all probability distributions are possible, but surprisingly the uniform distribution is possible for $\{1,2,4,8,16\}$ possible drop locations. Furthermore, every probability distribution can be approximated arbitrarily closely, and every dyadic probability distribution can be divided by a suitable power of $2$ and then constructed exactly (along with extra "junk" outputs). In a more general model, if a ball hits a pin off center, it falls left or right accordingly. Then we prove a universality result: any distribution of $n$ dyadic probabilities, each specified by $k$ bits, can be constructed using $O(n k^2)$ pins, which is close to the information-theoretic lower bound of $Ω(n k)$.