Games on triangulations
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).
|Keywords||Algorithms, Combinatorial games, Geometry, Planar triangulations|
|Journal||Theoretical Computer Science|
Aichholzer, O. (Oswin), Bremner, D. (David), Demaine, E.D. (Erik D.), Hurtado, F. (Ferran), Kranakis, E, Krasser, H. (Hannes), … Urrutia, J. (Jorge). (2005). Games on triangulations. Theoretical Computer Science, 343(1-2), 42–71. doi:10.1016/j.tcs.2005.05.007