David Eppstein - Publications

Publications with Yushi Uno

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

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

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