David Eppstein - Publications

Folding and unfolding

• A disk-packing algorithm for an origami magic trick.
  M. Bern, E. Demaine, D. Eppstein, and B. Hayes.
  Int. Conf. Fun with Algorithms, Elba, June 1998.
  Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 32–42.
  Origami³: Proc. 3rd Int. Mtg. Origami Science, Math, and Education (Asilomar, California, 2001), A K Peters, 2002, pp. 17–28.

  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.

• Ununfoldable polyhedra.
  M. Bern, E. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Snoeyink.
  arXiv:cs.CG/9908003.
  Tech. rep. CS-99-04, Univ. of Waterloo, Dept. of Computer Science, Aug. 1999.
  11th Canad. Conf. Comp. Geom., 1999.
  4th CGC Worksh. Computational Geometry, Johns Hopkins Univ., 1999.
  Comp. Geom. Theory & Applications (special issue for 4th CGC Worksh.) 24 (2): 51–62, 2003.

  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.

• Hinged dissections of polyominos and polyforms.
  E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.
  arXiv:cs.CG/9907018.
  11th Canad. Conf. Comp. Geom., 1999.
  Computational Geometry: Theory and Applications 31 (3): 237–262, 2005 (special issue for 11th CCCG).

  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.

• Hinged kite mirror dissection.
  D. Eppstein.
  arXiv:cs.CG/0106032.

  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.

• Vertex-unfoldings of simplicial manifolds.
  E. Demaine, D. Eppstein, J. Erickson, G. Hart, and J. O'Rourke.
  Tech. Reps. 071 and 072, Smith College, 2001.
  arXiv:cs.CG/0107023 and cs.CG/0110054.
  18th ACM Symp. Comp. Geom., Barcelona, 2002, pp. 237–243.
  Discrete Geometry: In honor of W. Kuperberg's 60th birthday, Pure and Appl. Math. 253, Marcel Dekker, pp. 215–228, 2003.

  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

  (Jeff's pubs page)

• Flat foldings of plane graphs with prescribed angles and edge lengths.
  Z. Abel, E. Demaine, M. Demaine, D. Eppstein, A. Lubiw, and R. Uehara.
  arXiv:1408.6771.
  22nd Int. Symp. Graph Drawing, Würzburg, Germany, 2014.
  Springer, Lecture Notes in Comp. Sci. 8871, 2014, pp. 272–283.
  J. Computational Geometry 9 (1): 74–93, 2018.

  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.

• Minimum forcing sets for Miura folding patterns.
  B. Ballinger, M. Damian, D. Eppstein, R. Flatland, J. Ginepro, and T. Hull.
  arXiv:1410.2231.
  26th ACM-SIAM Symp. on Discrete Algorithms, San Diego, 2015, pp. 136–147.

  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)

• Folding a paper strip to minimize thickness.
  E. Demaine, D. Eppstein, A. Hesterberg, H. Ito, A. Lubiw, R. Uehara, and Y. Uno.
  arXiv:1411.6371.
  9th International Workshop on Algorithms and Computation (WALCOM 2015), Dhaka, Bangladesh.
  Springer, Lecture Notes in Comp. Sci. 8973 (2015), pp. 113–124.
  Journal of Discrete Algorithms 36: 18–26, 2016 (special issue for WALCOM).
  

  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.

• Folding polyominoes into (poly)cubes.
  O. Aichholzer, M. Biro, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, A. Hesterberg, I. Kostitsyna, and C. Schmidt.
  27th Canadian Conference on Computational Geometry, Kingston, Ontario, Canada, 2015, pp. 101–106.
  arXiv:1712.09317.
  Int. J. Comp. Geom. & Appl. 28 (3): 197–226, 2018.

  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.

• Rigid origami vertices: Conditions and forcing sets.
  Z. Abel, J. Cantarella, E. Demaine, D. Eppstein, T. Hull, J. Ku, R. Lang, and T. Tachi.
  arXiv:1507.01644.
  J. Computational Geometry 7 (1): 171–184, 2016.

  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.

• Realization and connectivity of the graphs of origami flat foldings.
  D. Eppstein.
  arXiv:1808.06013.
  Proc. 26th Int. Symp. Graph Drawing, Barcelona, 2018.
  Springer, Lecture Notes in Comp. Sci. 11282 (2018), pp. 541–554.
  J. Computational Geometry 10 (1): 257–280, 2019.

  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)

• Ununfoldable Polyhedra with 6 Vertices or 6 Faces.
  H. A. Akitaya, E. Demaine, D. Eppstein, T. Tachi, and R. Uehara.
  22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³), Tokyo, Japan, 2019, pp. 27–28.
  Comp. Geom. Theory & Applications 103: 101857, 2022.
  

  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 JCDCG³ version used the title "Minimal ununfoldable polyhedron".

• Some polycubes have no edge-unzipping.
  E. Demaine, M. Demaine, D. Eppstein, and J. O'Rourke.
  arXiv:1907.08433.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 101–105.
  Geombinatorics 31 (3): 101–109, 2022.
  

  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.

• Face flips in origami tessellations.
  H. A. Akitaya, V. Dujmović, D. Eppstein, T. Hull, K. Jain, and A. Lubiw.
  arXiv:1910.05667.
  J. Computational Geometry 11 (1): 397–417, 2020.

  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.

• Acutely triangulated, stacked, and very ununfoldable polyhedra.
  E. Demaine, M. Demaine, and D. Eppstein.
  arXiv:2007.14525.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 106–113.

  We construct non-convex but topologically spherical polyhedra in which all faces are acute triangles, with no unfolded net.

• Locked and unlocked smooth embeddings of surfaces.
  D. Eppstein.
  arXiv:2206.12989.
  34th Canadian Conference on Computational Geometry, 2022, pp. 135–142.
  Computing in Geometry and Topology 2 (2): 5.1–5.20, 2023.

  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)

• A parameterized algorithm for flat folding.
  D. Eppstein.
  arXiv:2306.11939.
  Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 35–42.
  

  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.

  Merged into "Computational complexities of folding" for journal submission.

• Computational complexities of folding.
  D. Eppstein.
  Invited talk, 8th International Meeting on Origami in Science, Mathematics and Education, Melbourne, Australia, 2024.
  Invited talk, 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2024.
  arXiv:2410.07666.
  Journal of Information Processing 33: 954–973, 2025.

  We survey known hardness results on folding origami and prove several new ones: finding a flat-folded state is \(\mathsf{NP}\)-hard, but fixed-parameter tractable in a combination of ply and the treewidth of an associated graph. Finding a 3d-folded state cannot be expressed in closed form and cannot be computed by bounded-degree algebraic-root primitives. Reconfiguring certain systems of overlapping origami squares, hinged to a table at one edge, is \(\mathsf{PSPACE}\)-complete, and counting the number of configurations is \(\#\mathsf{P}\)-complete. Testing flat-foldability of infinite fractal folding patterns (even on normal square origami paper) is undecidable.