Playing with Triangulations

Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado, Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia, Jorge Urrutia

Research output: Chapter in Book/Report/Conference proceedingChapter

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. 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.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJin Akiyama, Mikio Kano
PublisherSpringer Verlag
Pages22-37
Number of pages16
ISBN (Print)3540207767, 9783540207764
DOIs
StatePublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2866
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Playing with Triangulations'. Together they form a unique fingerprint.

Cite this