Zobrazeno 1 - 10
of 1 093
pro vyhledávání: '"Demaine, Erik"'
Autor:
Ani, Hayashi, Chung, Lily, Demaine, Erik D., Diomidova, Jenny, Hendrickson, Della, Lynch, Jayson
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (introduced in 1999). The proof also extends to Push-$k$ for any $k \ge 2$. We also prove PSPACE-completeness of two versions
Externí odkaz:
http://arxiv.org/abs/2412.20079
Autor:
Demaine, Erik D., Demaine, Martin L., Hecher, Markus, Lin, Rebecca, Luo, Victor H., Nara, Chie
We prove two results about transforming any convex polyhedron, modeled as a linkage L of its edges. First, if we subdivide each edge of L in half, then L can be continuously flattened into a plane. Second, if L is equilateral and we again subdivide e
Externí odkaz:
http://arxiv.org/abs/2412.15130
Autor:
Chung, Lily, Demaine, Erik D., Demaine, Martin L., Hecher, Markus, Lin, Rebecca, Lynch, Jayson, Nara, Chie
We analyze the problem of folding one polyhedron, viewed as a metric graph of its edges, into the shape of another, similar to 1D origami. We find such foldings between all pairs of Platonic solids and prove corresponding lower bounds, establishing t
Externí odkaz:
http://arxiv.org/abs/2412.15121
In 1907, Henry Ernest Dudeney posed a puzzle: ``cut any equilateral triangle \dots\ into as few pieces as possible that will fit together and form a perfect square'' (without overlap, via translation and rotation). Four weeks later, Dudeney demonstra
Externí odkaz:
http://arxiv.org/abs/2412.03865
Autor:
Chung, Lily, Demaine, Erik D., Diomidova, Jenny, Kamata, Tonan, Lynch, Jayson, Uehara, Ryuhei, Zhang, Hanyu Alice
We prove that, for any two polyhedral manifolds P, Q, there is a polyhedral manifold I such that P, I share a common unfolding and I, Q share a common unfolding. In other words, we can unfold P, refold (glue) that unfolding into I, unfold I, and then
Externí odkaz:
http://arxiv.org/abs/2412.02174
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:
Demaine, Erik D., Langerman, Stefan
We prove that the following problem is co-RE-complete and thus undecidable: given three simple polygons, is there a tiling of the plane where every tile is an isometry of one of the three polygons (either allowing or forbidding reflections)? This res
Externí odkaz:
http://arxiv.org/abs/2409.11582
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 Hardness Group, Anchaleenukoon, Nithid, Dang, Alex, Demaine, Erik D., Ji, Kaylee, Saengrungkongka, Pitchayut
Given a chain of $HW$ cubes where each cube is marked "turn $90^\circ$" or "go straight", when can it fold into a $1 \times H \times W$ rectangular box? We prove several variants of this (still) open problem NP-hard: (1) allowing some cubes to be wil
Externí odkaz:
http://arxiv.org/abs/2407.10323
How should we thread a single string through a set of tubes so that pulling the string taut self-assembles the tubes into a desired graph? While prior work [ITCS 2024] solves this problem with the goal of minimizing the length of string, we study her
Externí odkaz:
http://arxiv.org/abs/2405.17953