Paper by Erik D. Demaine

Reference:

Sachio Teramoto, Erik Demaine, and Ryuhei Uehara, “The Voronoi game on graphs and its complexity”, Journal of Graph Algorithms and Applications, volume 15, number 4, 2011, pages 485–501.

BibTeX

@Article{VoronoiGame_JGAA,
  AUTHOR        = {Sachio Teramoto and Erik Demaine and Ryuhei Uehara},
  TITLE         = {The {Voronoi} game on graphs and its complexity},
  JOURNAL       = {Journal of Graph Algorithms and Applications},
  journalurl    = {http://jgaa.info/},
  VOLUME        = 15,
  NUMBER        = 4,
  YEAR          = 2011,
  PAGES         = {485--501},

  doi           = {https://dx.doi.org/10.7155/jgaa.00235},
  dblp          = {https://dblp.org/rec/journals/jgaa/TeramotoDU11},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.7155/jgaa.00235">JGAA</A>.},
  replaces      = {VoronoiGame_CIG2006},
  papers        = {VoronoiGame_CIG2006},
}

Abstract:

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.

Comments:

This paper is also available from JGAA.

Availability:

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)