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, “Playing with Triangulations”, in Revised Papers from the Japan Conference on Discrete and Computational Geometry (JCDCG 2002), Lecture Notes in Computer Science, volume 2866, Tokyo, Japan, December 6–9, 2002, pages 22–37.
We analyze several perfect-information combinatorial games
played on planar triangulations. We introduce three broad categories of
such games: constructing, transforming, and marking triangulations. In
various situations, we develop polynomial-time algorithms to determine
who wins a given game under optimal play, and to find a winning strategy.
Along the way, we show connections to existing combinatorial games
such as Kayles.
- The paper is \copyright Springer-Verlag.
- The paper is 17 pages.
- The paper is available in PostScript (2338k), gzipped PostScript (1118k), and PDF (198k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- TriangulationGames_TCS (Games on Triangulations)
- TriangulationGames_EuroCG2003 (Geometric Games on Triangulations)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated October 19, 2020 by