Geometric Games on Triangulations

O. Aichholzer, D. Bremner, E. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, and J. Urrutia

Abstract:

We analyze several perfect-information combinatorial games played on planar triangulations. We describe main broad categories of these games and provide in various situations polynomial-time algorithms to determine who wins a given game under optimal play, and ideally, to find a winning strategy. Relations to relevant existing combinatorial games, such as Kayles, are also shown.

Reference: O. Aichholzer, D. Bremner, E. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, and J. Urrutia. Geometric games on triangulations. In Proc. $19^{th}$ European Workshop on Computational Geometry CG '03 Bonn, pages 89-92, Bonn, Germany, 2003.