JAIST Repository >
School of Information Science >
Articles >
Journal Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10119/13767

Title: Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set
Authors: Horiyama, Takashi
Kiyomi, Masashi
Okamoto, Yoshio
Uehara, Ryuhei
Uno, Takeaki
Uno, Yushi
Yamauchi, Yukiko
Keywords: combinatorial game
sankaku-tori
pencil-and-paper puzzle
NP-complenetess
Issue Date: 2014-07-01
Publisher: Springer
Magazine name: Lecture Notes in Computer Science
Volume: 8496
Start page: 230
End page: 239
DOI: 10.1007/978-3-319-07890-8_20
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.
Rights: This is the author-created version of Springer, Takashi Horiyama, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno and Yukiko Yamauchi, Lecture Notes in Computer Science, 8496, 2014, 230-239. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-319-07890-8_20
URI: http://hdl.handle.net/10119/13767
Material Type: author
Appears in Collections:b10-1. 雑誌掲載論文 (Journal Articles)

Files in This Item:

File Description SizeFormat
20267.pdf118KbAdobe PDFView/Open

All items in DSpace are protected by copyright, with all rights reserved.

 


Contact : Library Information Section, JAIST (ir-sys[at]ml.jaist.ac.jp)