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.

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

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

Semi-automatically filtered from a common source file.