The one-round Voronoi game replayed

摘要

We consider the one-round Voronoi game, where the first player ("White", called "Wilma") places a set of n points in a rectangular area of aspect ratio rho less than or equal to 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 rho = 1, Barney has a strategy that guarantees a fraction of 1/2 + alpha, for some small fixed alpha.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 greater than or equal to 3 and rho > root2, and for n = 2 and p > root3/2. Wilma wins in all remaining cases, i.e., for n greater than or equal to 3 and rho less than or equal to root2, for n = 2 and rho less than or equal to root3/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. (C) 2004 Elsevier B.V. All rights reserved.