Advantage in the discrete Voronoi game

DOI10.7155/JGAA.00331zbMATH Open1302.05118arXiv1303.0523OpenAlexW2090004555MaRDI QIDQ2929591FDOQ2929591

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

Publication date: 13 November 2014

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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 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 one-round game on the same graph.

Full work available at URL: https://arxiv.org/abs/1303.0523

Recommendations

• The Voronoi game on graphs and its complexity
• The one-round Voronoi game
• Two-round discrete Voronoi game along a line
• The one-round multi-player discrete Voronoi game on grids and trees
• The one-round multi-player discrete Voronoi game on grids and trees

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cited In (9)

• The one-round Voronoi game replayed
• The discrete Voronoi game in \(\mathbb{R}^2\)
• The Voronoi game on graphs and its complexity
• The inverse Voronoi problem in graphs. I: Hardness
• The one-round multi-player discrete Voronoi game on grids and trees
• The one-round multi-player discrete Voronoi game on grids and trees
• Nash equilibria in reverse temporal Voronoi games
• Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game
• Competitive location problems: balanced facility location and the one-round Manhattan Voronoi game

Uses Software

• MathOverflow

This page was built for publication: Advantage in the discrete Voronoi game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2929591)