Playing with Triangulations

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

doi:https://doi.org/10.1007/978-3-540-44400-8_4

Playing with Triangulations

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

Rutgers, The State University

Research output: Chapter in Book/Report/Conference proceeding › Chapter

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 language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Jin Akiyama, Mikio Kano
Publisher	Springer Verlag
Pages	22-37
Number of pages	16
ISBN (Print)	3540207767, 9783540207764
DOIs	https://doi.org/10.1007/978-3-540-44400-8_4
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2866

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

https://doi.org/10.1007/978-3-540-44400-8_4

Cite this

Aichholzer, O., Bremner, D., Demaine, E. D., Hurtado, F., Kranakis, E., Krasser, H., Ramaswami, S., Sethia, S., & Urrutia, J. (2003). Playing with Triangulations. In J. Akiyama, & M. Kano (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 22-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2866). Springer Verlag. https://doi.org/10.1007/978-3-540-44400-8_4

Aichholzer, Oswin ; Bremner, David ; Demaine, Erik D. et al. / Playing with Triangulations. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Jin Akiyama ; Mikio Kano. Springer Verlag, 2003. pp. 22-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{fb4759f477654edf901471a4ac7b02e6,

title = "Playing with 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. 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.",

author = "Oswin Aichholzer and David Bremner and Demaine, {Erik D.} and Ferran Hurtado and Evangelos Kranakis and Hannes Krasser and Suneeta Ramaswami and Saurabh Sethia and Jorge Urrutia",

year = "2003",

doi = "https://doi.org/10.1007/978-3-540-44400-8_4",

language = "English (US)",

isbn = "3540207767",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "22--37",

editor = "Jin Akiyama and Mikio Kano",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Aichholzer, O, Bremner, D, Demaine, ED, Hurtado, F, Kranakis, E, Krasser, H, Ramaswami, S, Sethia, S & Urrutia, J 2003, Playing with Triangulations. in J Akiyama & M Kano (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2866, Springer Verlag, pp. 22-37. https://doi.org/10.1007/978-3-540-44400-8_4

Playing with Triangulations. / Aichholzer, Oswin; Bremner, David; Demaine, Erik D. et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Jin Akiyama; Mikio Kano. Springer Verlag, 2003. p. 22-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2866).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - Playing with Triangulations

AU - Aichholzer, Oswin

AU - Bremner, David

AU - Demaine, Erik D.

AU - Hurtado, Ferran

AU - Kranakis, Evangelos

AU - Krasser, Hannes

AU - Ramaswami, Suneeta

AU - Sethia, Saurabh

AU - Urrutia, Jorge

PY - 2003

Y1 - 2003

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

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

UR - http://www.scopus.com/inward/record.url?scp=35248897723&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248897723&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/978-3-540-44400-8_4

DO - https://doi.org/10.1007/978-3-540-44400-8_4

M3 - Chapter

SN - 3540207767

SN - 9783540207764

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 22

EP - 37

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Akiyama, Jin

A2 - Kano, Mikio

PB - Springer Verlag

ER -

Aichholzer O, Bremner D, Demaine ED, Hurtado F, Kranakis E, Krasser H et al. Playing with Triangulations. In Akiyama J, Kano M, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 22-37. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: https://doi.org/10.1007/978-3-540-44400-8_4

Playing with Triangulations

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this