Today I read a paper titled “The one-round Voronoi game replayed”

The abstract is:

* We consider the one-round Voronoi game, where player one (“White”, called “Wilma”) places a set of n points in a rectangular area of aspect ratio r <=1, followed by the second player (``Black'', called ``Barney''), who places the same number of points.*

*Each player wins the fraction of the board closest to one of his points, and the goal is to win more than half of the total area.*

*This problem has been studied by Cheong et al., who showed that for large enough $n$ and r=1, Barney has a strategy that guarantees a fraction of 1/2+a, for some small fixed a.*

*We resolve a number of open problems raised by that paper.*

*In particular, we give a precise characterization of the outcome of the game for optimal play: We show that Barney has a winning strategy for n>2 and r>sqrt{2}/n, and for n=2 and r>sqrt{3}/2.*

*Wilma wins in all remaining cases, i.e., for n>=3 and r<=sqrt{2}/n, for n=2 and r<=sqrt{3}/2, and for n=1.*

*We also discuss complexity aspects of the game on more general boards, by proving that for a polygon with holes, it is NP-hard to maximize the area Barney can win against a given set of points by Wilma.*