David Eppstein – Publications

Publications with Martin Demaine

• 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.

• Phutball endgames are hard.
  E. Demaine, M. Demaine, and D. Eppstein.
  arXiv:cs.CC/0008025.
  More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 351–360.

  We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.

  (Erik's publications 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.

• 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.

• 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.

• Existence and hardness of conveyor belts.
  M. Baird, S. C. Billey, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, G. Gordon, S. Griffin, J. S. B. Mitchell, and J. P. Swanson.
  arXiv:1908.07668.
  Electronic J. Combinatorics 27 (4), Paper P4.25, 2020.

  A conveyor belt is a tight simple closed curve that touches each of a given set of disjoint disks. We show that certain special families of disks always have a conveyor belt, but that it is NP-complete to tell whether one exists for arbitrary families of disks. It is always possible to add a linear number of "guide disks" to a given set of disks to allow them to be connected by a conveyor belt.

• 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.

• New results in sona drawing: hardness and TSP separation.
  M.-W. Chiu, E. Demaine, M. Demaine, D. Eppstein, R. Hearn, A. Hesterberg, M. Korman, I. Parada, and M. Rudoy.
  arXiv:2007.15784.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 63–72.

  A sona drawing is a self-crossing curve in the plane that separates each of a given system of points into its own region. We show that it is hard to find the shortest such curve, and we explore how much shorter than the TSP it can be.

• Multifold tiles of polyominoes and convex lattice polygons.
  K. Chida, E. Demaine, M. Demaine, D. Eppstein, A. Hesterberg, T. Horiyama, J. Iacono, H. Ito, S. Langerman, R. Uehara, and Y. Uno.
  23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2021, pp. 28–29.
  Thai Journal of Mathematics 21 (4): 957–978, 2023.

  We investigate shapes whose congruent copies can cover the plane exactly \(k\) times per point, but not a number of times that is a nonzero integer smaller than \(k\). We find polyominoes with this property for all \(k\ge 2\), and convex integer-coordinate polygons with this property for \(k=5\) and for all \(k\ge 7\).

• Geodesic paths passing through all faces on a polyhedron.
  E. Demaine, M. Demaine, D. Eppstein, H. Ito, Y. Katayama, W. Maruyama, and Y. Uno.
  24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, September 9–11, 2022.
  Springer, Lecture Notes in Comp. Sci. 14364 (2026), pp. 184–209.

  Which convex polyhedra have the property that there exist two points on the surface of the polyhedron whose shortest path passes through all of the faces of the polyhedron? The answer is yes for the tetrahedron, and for certain prisms, but no for all other regular polyhedra.