Journal article
Games on triangulations
Abstract
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 …
Authors
Aichholzer O; Bremner D; Demaine ED; Hurtado F; Kranakis E; Krasser H; Ramaswami S; Sethia S; Urrutia J
Journal
Theoretical Computer Science, Vol. 343, No. 1-2, pp. 42–71
Publisher
Elsevier
Publication Date
10 2005
DOI
10.1016/j.tcs.2005.05.007
ISSN
0304-3975