Otfried Cheong, Sariel Har-Peled, Nathan Linial, and Jiri Matousek
In the one-round Voronoi game, the first player places n
sites inside a unit-square Q. Next, the second player places
n points inside Q. The payoff for a player is the total
area of the Voronoi region of Q under their control. In this
paper, we show that the second player can always place the points in
such a way that it controls 1/2 + alpha fraction of the total
area of Q, where alpha>0 is a constant independent of
n.
Paper -
Postscript,
PDF.
@string{DCG = "Discrete Comput. Geom."}
@article{chlm-orvg-04,
title = "The One-Round {Voronoi} Game",
author = "O. Cheong and S.~{Har-Peled} and N. Linial and
J. Matousek",
journal = DCG,
volume = 31,
number = 1,
pages = {125--138},
year = 2004
}