Playing with 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. 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.
|Organisation||School of Computer Science|
Aichholzer, O. (Oswin), Bremner, D. (David), Demaine, E.D. (Erik D.), Hurtado, F. (Ferran), Kranakis, E, Krasser, H. (Hannes), … Urrutia, J. (Jorge). (2003). Playing with Triangulations.