The one-round Voronoi game
Otfried Cheong, Sariel Har-Peled, Nathan Linial, Jiřı́ Matoušek · 2002
(MATH) In the one-round Voronoi game, the first player chooses an n-point set $\PFRST$ in a square $Q$, and then the second player places another n-point set $\PSCND$ into $Q$. The payoff for the second player is the fraction of the area of $Q$ occupied by the regions of the points of $\PSCND$ in the Voronoi diagram of $\PFRST\cup\PSCND$. We give a strategy for the second player that always guarantees him a payoff of at least $\frac12+\alpha$, for a constant $\alpha>0$ independent of n. This contrasts with the one-dimensional situation, with $Q=[0,1]$, where the first player can always win more than 1/2.