Home Bookmarks Papers Blog

The One-Round Voronoi Game

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
}

Last modified: Thu Jan 22 09:51:38 CST 2004