Paper by Erik D. Demaine
- Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, and Jorge Urrutia, “Games on Triangulations”, Theoretical Computer Science, volume 343, number 1–2, October 2005, pages 42–71. Special issue ``Game Theory Meets Theoretical Computer Science''.
We analyze several perfect-information combinatorial games
played on planar triangulations.
We introduce three broad categories of such games—constructing,
transforming, and marking triangulations—and several specific games
within each category.
In various situations of each game, we develop polynomial-time algorithms
to determine who wins a given game position under optimal play,
and to find a winning strategy.
Along the way, we show connections to existing combinatorial games
such as Kayles and Nimstring (a variation on Dots-and-Boxes).
- This paper is also available from ScienceDirect.
- The paper is 32 pages.
- The paper is available in PostScript (1636k), gzipped PostScript (625k), and PDF (293k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- TriangulationGames_JCDCG2002 (Playing with Triangulations)
- TriangulationGames_EuroCG2003 (Geometric Games on Triangulations)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 27, 2017 by