## Dániel Gerbner, Viola Mészáros, Dömötör
Pálvölgyi, Alexey Pokrovskiy, and Günter Rote:

# Advantage in the discrete Voronoi game

*Journal of Graph Algorithms and
Applications* **18**, no. 3 (2014),
439–455. doi:10.7155/jgaa.00331*. arXiv:1303.0523 [math.CO].
*
### 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 bounded-degree graphs. For trees, the first player can get
at least a quarter of the vertices, and we give examples where she
can get only little more than a third of them. We make some general
observations, relating the result with many rounds to the result for the
one-round game on the same graph.

Last update: November 7, 2014.