Did you know that any straight-line drawing on paper can be folded so that the complete drawing can be cut out with one straight scissors cut? That there is a planar linkage that can trace out any ...algebraic curve, or even 'sign your name'? Or that a 'Latin cross' unfolding of a cube can be refolded to 23 different convex polyhedra? Over the past decade, there has been a surge of interest in such problems, with applications ranging from robotics to protein folding. With an emphasis on algorithmic or computational aspects, this treatment gives hundreds of results and over 60 unsolved 'open problems' to inspire further research. The authors cover one-dimensional (1D) objects (linkages), 2D objects (paper), and 3D objects (polyhedra). Aimed at advanced undergraduate and graduate students in mathematics or computer science, this lavishly illustrated book will fascinate a broad audience, from school students to researchers.
Computational flattening algorithms have been successfully applied to X-ray microtomography scans of damaged historical documents, but have so far been limited to scrolls, books, and documents with ...one or two folds. The challenge tackled here is to reconstruct the intricate folds, tucks, and slits of unopened letters secured shut with "letterlocking," a practice-systematized in this paper-which underpinned global communications security for centuries before modern envelopes. We present a fully automatic computational approach for reconstructing and virtually unfolding volumetric scans of a locked letter with complex internal folding, producing legible images of the letter's contents and crease pattern while preserving letterlocking evidence. We demonstrate our method on four letterpackets from Renaissance Europe, reading the contents of one unopened letter for the first time. Using the results of virtual unfolding, we situate our findings within a novel letterlocking categorization chart based on our study of 250,000 historical letters.
This paper presents an end-to-end approach to automate the design and fabrication process for self-folding origami structures. Self-folding origami structures are robotic sheets composed of rigid ...tiles and joint actuators. When they are exposed to heat, each joint folds into a preprogrammed angle. Those folding motions transform themselves into a structure, which can be used as body of 3-D origami robots, including walkers, analog circuits, rotational actuators, and microcell grippers. Given a 3-D model, the design algorithm automatically generates a layout printing design of the sheet form of the structure. The geometric information, such as the fold angles and the folding sequences, is embedded in the sheet design. When the sheet is printed and baked in an oven, the sheet self-folds into the given 3-D model. We discuss, first, the design algorithm generating multiple-step self-folding sheet designs, second, verification of the algorithm running in <inline-formula><tex-math notation="LaTeX">O(n^2)</tex-math> </inline-formula> time, where <inline-formula><tex-math notation="LaTeX">n</tex-math></inline-formula> is the number of the vertices, third, implementation of the algorithm, and finally, experimental results, several self-folded 3-D structures with up to 55 faces and two sequential folding steps.
On the complexity of reconfiguration problems Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J.A. ...
Theoretical computer science,
03/2011, Letnik:
412, Številka:
12
Journal Article
Recenzirano
Odprti dostop
Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that ...a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time.
Origami-inspired manufacturing can produce complex structures and machines by folding two-dimensional composites into three-dimensional structures. This fabrication technique is potentially less ...expensive, faster, and easier to transport than more traditional machining methods, including 3-D printing. Self-folding enhances this method by minimizing the manual labor involved in folding, allowing for complex geometries and enabling remote or automated assembly. This paper demonstrates a novel method of self-folding hinges using shape memory polymers (SMPs), paper, and resistive circuits to achieve localized and individually addressable folding at low cost. A model for the torque exerted by these composites was developed and validated against experimental data, in order to determine design rules for selecting materials and designing hinges. Torque was shown to increase with SMP thickness, resistive circuit width, and supplied electrical current. This technique was shown to be capable of complex geometries, as well as locking assemblies with sequential folds. Its functionality and low cost make it an ideal basis for a new type of printable manufacturing based on two-dimensional fabrication techniques.
Suppose that we are given two independent sets Ib and Ir of a graph such that |Ib|=|Ir|, and imagine that a token is placed on each vertex in Ib. Then, the sliding token problem is to determine ...whether there exists a sequence of independent sets which transforms Ib into Ir so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between Ib and Ir whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length.
Consider an agent traversing a graph of “gadgets”, where each gadget has local state that changes with each traversal by the agent according to specified rules. Prior work has studied the ...computational complexity of deciding whether the agent can reach a specified location, a problem we call
reachability
. This paper introduces new goals for the agent, aiming to characterize when the computational complexity of these problems is the same or differs from that of reachability. First we characterize the complexity of
universal traversal
—where the goal is to traverse every gadget at least once—for DAG gadgets (partially), one-state gadgets, and reversible deterministic gadgets. Then we study the complexity of
reconfiguration
—where the goal is to bring the system of gadgets to a specified state. We prove many cases PSPACE-complete, and show in some cases that reconfiguration is strictly harder than reachability, while in other cases, reachability is strictly harder than reconfiguration.
We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph ...model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the “Generalized Rush Hour Logic” developed by Flake and Baum Theoret. Comput. Sci. 270(1–2) (2002) 895.
We illustrate the importance of our model of computation by giving simple reductions to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (
1
×
2
blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour
TM
puzzles are PSPACE-complete Theoret. Comput. Sci. 270(1–2) (2002) 895, of which we also give a simpler proof. We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem Int. J. Robot. Res. 3(4) (1984) 76, a classic motion-planning problem. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete In: Proc. Internat. Conf. on Fun with Algorithms, Elba, Italy, June 1998, pp. 65–76., by showing that it is PSPACE-complete even if no barriers are allowed.
We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario ...Bros. 1–3, The Lost Levels, and Super Mario World; Donkey Kong Country 1–3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.
Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is ...to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n2) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.
PDF
