The one-round Voronoi game replayed
Sándor P. Fekete, Henk Meijer · arXiv (Cornell University) · 2003
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 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.