9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

Discrete Voronoi Game

Presented by Dr. Viola MéSZáROS
Type: Oral presentation
Track: Discrete and Computational Geometry

Content

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.

Place

Location: Koper, Slovenia

Primary authors

More

Co-authors

More