Journal of Graph Algorithms and Applications · 2011 · 25 citations · 3 references
ComputingComputer ScienceAlgorithmsFacility LocationGame TheoryAlgorithmic Game TheoryCombinatorial Game TheoryCombinatorial OptimizationCompetitive Facility LocationComputational ComplexityVoronoi DiagramsDiscrete Competitive Facility LocationDiscrete Voronoi DiagramsFacility Location On GraphsGraph GamesVoronoi Cells
The Voronoi game is a two-person game which is a model for a competitive facility location.The game is done on a continuous domain, and only two special cases (1-dimensional case and 1-round case) are well investigated.We introduce the discrete Voronoi game of 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 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.
3
Competitive facility location: the Voronoi game
Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong et al. · Theoretical Computer Science · 2003 · 118 citations · Full text
Management, Industrial Engineering, Operations Management +14
The one-round Voronoi game replayed
Sándor P. Fekete, Henk Meijer · Computational Geometry · 2004 · 47 citations