David Eppstein - Publications

Publications with Adam Herterberg

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

• Reconfiguring undirected paths.
  E. Demaine, D. Eppstein, A. Hesterberg, K. Jain, A. Lubiw, R. Uehara, and Y. Uno.
  arXiv:1905.00518.
  16th Algorithms and Data Structures Symp. (WADS 2019), Edmonton, Alberta.
  Springer, Lecture Notes in Comp. Sci. 11646 (2019), pp. 353–365.
  

  A motion that slides an undirected path along its length from one configuration to another in a graph (allowing moves in both directions) can be found in time that is fixed-parameter tractable in the path length. However the problem is PSPACE-complete for paths of unbounded length, even when the host graph has bounded bandwidth.

  (Slides)

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