David Eppstein - Publications

Publications with Erik Demaine

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

  (preprint at Erik's web site -- BibTeX -- CiteSeer)

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

  (BibTeX -- Erik's publication page -- CiteSeer -- ACM DL)

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

  (BibTeX -- Erik's CCCG publication page -- Erik's CGTA publication page -- Citations)

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

  (BibTeX -- Citations -- Erik's publications page -- CiteSeer)

• 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

  (BibTeX -- Jeff's pubs page)

Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.