We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.
We prove the existence of polyhedra in which all faces are convex, but which can not be cut along edges and folded flat.
Note variations in different versions: the CCCG one was only Bern, Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable polyhedra with triangular faces". The journal version uses the title "Ununfoldable polyhedra with convex faces" and the combined results from both conference versions.
We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.
We show that any polygon can be cut into kites, connected into a chain by hinges at their vertices, and that this hinged assemblage can be unfolded and refolded to form the mirror image of the polygon.
We unfold any polyhedron with triangular faces into a planar layout in which the triangles are disjoint and are connected in a sequence from vertex to vertex
Given a plane graph with fixed edge lengths, and an assignment of the angles 0, 180, and 360 to the angles between adjacent edges, we show how to test whether the angle assignment can be realized by an embedding of the graph as a flat folding on a line. As a consequence, we can determine whether two-dimensional cell complexes with one vertex can be flattened. The main idea behind the result is to show that each face of the graph can be folded independently of the other faces.
A forcing set for an origami crease pattern is a subset of the folds with the property that, if these folds are folded the correct way (mountain vs valley) the rest of the pattern also has to be folded the correct way. We use a combinatorial equivalence with three-colored grids to construct minimum-cardinality forcing sets for the Miura-ori folding pattern and for other patterns with differing folds along the same line segments.
(Slides)
If a folding pattern for a flat origami is given, together with a mountain-valley assignment, there might still be multiple ways of folding it, depending on how some flaps of the pattern are arranged within pockets formed by folds elsewhere in the pattern. It turns out to be hard (but fixed-parameter tractable) to determine which of these ways is best with respect to minimizing the thickness of the folded pattern.
We classify the polyominoes that can be folded to form the surface of a cube or polycube, in multiple different folding models that incorporate the type of fold (mountain or valley), the location of a fold (edges of the polycube only, or elsewhere such as along diagonals), and whether the folded polyomino is allowed to pass through the interior of the polycube or must stay on its surface.
We give an exact characterization of the one-vertex origami folding patterns that can be folded rigidly, without bending the parts of the paper between the folds.
If you fold a piece of paper flat and unfold it again, the resulting crease pattern forms a planar graph. We prove that a tree can be realized in this way (with its leaves as diverging rays that reach the boundary of the paper) if and only if all internal vertices have odd degree greater than two. On the other hand, for a folding pattern on an infinite sheet of paper with an added vertex at infinity as the endpoint of all its rays, the resulting graph must be 2-vertex-connected and 4-edge-connected.
(Slides)
We find a (nonconvex, but topologically equivalent to convex) polyhedron with seven vertices and six faces that cannot be unfolded to a flat polygon by cutting along its edges. Both the number of vertices and the number of faces are the minimum possible. The JCDCG3 version used the title "Minimal ununfoldable polyhedron".
We find polycubes that cannot be cut along a simple path through their vertices and edges and unfolded to form a flat polygon in the plane.
We study problems in which we are given an origami crease pattern and seek to reconfigure one locally flat foldable mountain-valley assignment into another by a sequence of operations that change the assignment around a single face of the crease pattern.
We construct non-convex but topologically spherical polyhedra in which all faces are acute triangles, with no unfolded net.
If a subset of the plane has a continuous shrinking motion of itself, then every smooth isometric embedding of that subset into 3d can be smoothly flattened. However, there exist subsets of the plane with holes, for which some smooth embeddings that are topologically equivalent to a flat embedding cannot be smoothly flattened.
(Slides)
Testing whether an origami folding pattern can be folded flat is fixed-parameter tractable when parameterized by two parameters: the ply (maximum number of layers) of the folding, and the treewidth of a planar graph describing the arrangement of polygons in the flat-folded result. The dependence on treewidth is optimal under the exponential-time hypothesis.
Geometry – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.