Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00331
Advantage in the discrete Voronoi game
Dániel Gerbner,
Viola Mészáros,
Dömötör Pálvölgyi,
Alexey Pokrovskiy, and
Günter Rote
Vol. 18, no. 3, pp. 439457, 2014. Regular paper.
Abstract We study the discrete Voronoi game, where two players alternately claim vertices of a graph for t rounds. In the end, the remaining vertices are divided such that each player receives the vertices that are closer to his or her claimed vertices. We prove that there are graphs for which the second player gets almost all vertices in this game, but this is not possible for boundeddegree graphs. For trees, the first player can get at least one quarter of the vertices, and we give examples where she can get only little more than one third of them. We make some general observations, relating the result with many rounds to the result for the oneround game on the same graph.

Submitted: January 2014.
Reviewed: September 2014.
Revised: October 2014.
Accepted: October 2014.
Final: October 2014.
Published: October 2014.
Communicated by
Henk Meijer
