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 strategy for the second player that always guarantees him a payoff of at least 1/2 + α, for a constant α > 0 independent of 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 | 97-101 |
| Number of pages | 5 |
| DOIs | |
| State | Published - 2002 |
| Externally published | Yes |
| Event | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain Duration: Jun 5 2002 → Jun 7 2002 |
Other
| Other | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) |
|---|---|
| Country/Territory | Spain |
| City | Barcelona |
| Period | 6/5/02 → 6/7/02 |
Keywords
- Competitive Facility Location
- Voronoi diagram
- Voronoi game
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics