Sankaku-tori: An old Western-Japanese game played on a point set

Takashi Horiyama; Masashi Kiyomi; Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno; Yushi Uno; Yukiko Yamauchi

doi:10.1007/978-3-319-07890-8_20

Sankaku-tori: An old Western-Japanese game played on a point set

Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, Yukiko Yamauchi

Mathematical Informatics

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

1 Citation (Scopus)

Abstract

We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general.

Original language	English
Title of host publication	Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings
Publisher	Springer Verlag
Pages	230-239
Number of pages	10
ISBN (Print)	9783319078892
DOIs	https://doi.org/10.1007/978-3-319-07890-8_20
Publication status	Published - 2014
Event	7th International Conference on Fun with Algorithms, FUN 2014 - Sicily, Italy Duration: Jul 1 2014 → Jul 3 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8496 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	7th International Conference on Fun with Algorithms, FUN 2014
Country/Territory	Italy
City	Sicily
Period	7/1/14 → 7/3/14

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-07890-8_20

Cite this

Horiyama, T., Kiyomi, M., Okamoto, Y., Uehara, R., Uno, T., Uno, Y., & Yamauchi, Y. (2014). Sankaku-tori: An old Western-Japanese game played on a point set. In Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings (pp. 230-239). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8496 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-07890-8_20

Sankaku-tori: An old Western-Japanese game played on a point set. / Horiyama, Takashi; Kiyomi, Masashi; Okamoto, Yoshio et al.
Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings. Springer Verlag, 2014. p. 230-239 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8496 LNCS).

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

Horiyama, T, Kiyomi, M, Okamoto, Y, Uehara, R, Uno, T, Uno, Y & Yamauchi, Y 2014, Sankaku-tori: An old Western-Japanese game played on a point set. in Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8496 LNCS, Springer Verlag, pp. 230-239, 7th International Conference on Fun with Algorithms, FUN 2014, Sicily, Italy, 7/1/14. https://doi.org/10.1007/978-3-319-07890-8_20

Horiyama T, Kiyomi M, Okamoto Y, Uehara R, Uno T, Uno Y et al. Sankaku-tori: An old Western-Japanese game played on a point set. In Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings. Springer Verlag. 2014. p. 230-239. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-07890-8_20

Horiyama, Takashi ; Kiyomi, Masashi ; Okamoto, Yoshio et al. / Sankaku-tori : An old Western-Japanese game played on a point set. Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings. Springer Verlag, 2014. pp. 230-239 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0358fc587f454029b40997a09d829c7b,

title = "Sankaku-tori: An old Western-Japanese game played on a point set",

abstract = "We study a combinatorial game named {"}sankaku-tori{"} in Japanese, which means {"}triangle-taking{"} in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general.",

author = "Takashi Horiyama and Masashi Kiyomi and Yoshio Okamoto and Ryuhei Uehara and Takeaki Uno and Yushi Uno and Yukiko Yamauchi",

year = "2014",

doi = "10.1007/978-3-319-07890-8_20",

language = "English",

isbn = "9783319078892",

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

publisher = "Springer Verlag",

pages = "230--239",

booktitle = "Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings",

address = "Germany",

note = "7th International Conference on Fun with Algorithms, FUN 2014 ; Conference date: 01-07-2014 Through 03-07-2014",

}

TY - GEN

T1 - Sankaku-tori

T2 - 7th International Conference on Fun with Algorithms, FUN 2014

AU - Horiyama, Takashi

AU - Kiyomi, Masashi

AU - Okamoto, Yoshio

AU - Uehara, Ryuhei

AU - Uno, Takeaki

AU - Uno, Yushi

AU - Yamauchi, Yukiko

PY - 2014

Y1 - 2014

N2 - We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general.

AB - We study a combinatorial game named "sankaku-tori" in Japanese, which means "triangle-taking" in English. It is an old pencil-and-paper game for two players played in Western Japan. The game is played on points on the plane in general position. In each turn, a player adds a line segment to join two points, and the game ends when a triangulation of the point set is completed. The player who completes more triangles than the other wins. In this paper, we consider two restricted variants of this game. In the first variant, the first player always wins in a nontrivial way, and the second variant is NP-complete in general.

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

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

U2 - 10.1007/978-3-319-07890-8_20

DO - 10.1007/978-3-319-07890-8_20

M3 - Conference contribution

AN - SCOPUS:84903723690

SN - 9783319078892

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

SP - 230

EP - 239

BT - Fun with Algorithms - 7th International Conference, FUN 2014, Proceedings

PB - Springer Verlag

Y2 - 1 July 2014 through 3 July 2014

ER -

Sankaku-tori: An old Western-Japanese game played on a point set

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this