Abstract
In the one-round Voronoi game, the first player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payoff for the second player is the fraction of the area of Q occupied by the regions of the points of B in the Voronoi diagram of W ∪ B. We give a (randomized) strategy for the second player that always guarantees him a payoff of at least 1/2 + α, for a constant α > 0 and every large enough n. This contrasts with the one-dimensional situation, with Q = [0, 1], where the first player can always win more than 1/2.
Original language | English (US) |
---|---|
Pages (from-to) | 125-138 |
Number of pages | 14 |
Journal | Discrete and Computational Geometry |
Volume | 31 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2004 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics