Paper by Erik D. Demaine
- Sachio Teramoto, Erik Demaine, and Ryuhei Uehara, “Voronoi game on graphs and its complexity”, Journal of Graph Algorithms and Applications, volume 15, number 4, 2011, pages 485–501.
The Voronoi game is a two-person game which is a model for a competitive
facility location. The game is played on a continuous domain, and only two
special cases (one-dimensional case and one-round case) are well investigated.
We introduce the discrete Voronoi game in which the game arena is given
as a graph. We first analyze the game when the arena is a large complete
k-ary tree, and give an optimal strategy. When both players play
optimally, the first player wins when k is odd, and the game ends in a
tie for even k. Next we show that the discrete Voronoi game is
intractable in general. Even for the one-round case in which the strategy
adopted by the first player consist of a fixed single node, deciding whether
the second player can win is NP-complete. We also show that deciding whether
the second player can win is PSPACE-complete in general.
- This paper is also available from JGAA.
- The paper is available in PDF (242k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- VoronoiGame_CIG2006 (Voronoi game on graphs and its complexity)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 7, 2020 by