Best paper award for Mark de Berg, Sándor Kisfaludi-Bak and Mehran Mehr at ISAAC 2019
The paper On One-Round Discrete Voronoi Games by Mark de Berg (TU/e), Sándor Kisfaludi-Bak (former NETWORKS PhD student), and Mehran Mehr won the best-paper award at the 30th International Symposium on Algorithms and Computation (ISAAC 2019).
In a discrete Voronoi Game two players compete for a given set V of voters, who are modelled as points in some Euclidean space. An instance of the game specifies a voter set V , and integers k1 and k2. First, player P1 gets to select k1 locations in the Euclidean space, based on the positions of the voters in V. Next, player P2 gets to select k2 locations in the Euclidean space, based on the positions of the voters in V and the locations chosen by player P1. Player P1 wins a particular voter v if one of P1’s locations is closer to v than all P2’s locations. Player P1 wins the game if she wins the majority of the voters. The paper gives the first efficient algorithms for determining whether player P1 can win a given instance of the game.