Voronoi Game on a Path

摘要

ボロノイゲームは競合施設配置をモデル化した二人完全情報ゲームである．このゲームはもともと連続した領域上で考えられおり，その場合，1次元上の場合と，1ラウンドの場合については結論が出ている．最近，グラフ上で行なう離散ボロノイゲームが提案された．本研究ではパス上の離散ボロノイゲームに関して，完全な解析を行なう．%The Voronoi game is a two-person perfect information game modeling a competitive facility location. The original version of the game is played on a continuous domain. Only two special cases (1-dimensional case and 1-round case) are well investigated. Recently, the discrete Voronoi game of which the game arena is given as a graph was introduced. In this note, we give a complete analysis of the discrete Voronoi game on a path.