Voronoi game on graphs and its complexity
Sachio Teramoto, Erik D. Demaine, Ryuhei Uehara · 2006
The Voronoi game is a two-person game which is a model for competitive facility location. The game is played on a continuous domain, and only two special cases (the 1D case and the 1-round case) are well investigated. We introduce the discrete Voronoi game in which the game arena is given as a graph. We first show the best strategy when the game arena is a large complete k-ary tree. Next, we show that the discrete Voronoi game is intractable in general. Even in the 1-round case, and the place occupied by the first player is fixed, the game is NP-complete in general. We also show that the game is PSPACE-complete in general case