The one-round Voronoi game

ABSTRACT

(MATH) In the one-round Voronoi game, the first player chooses an n-point set $\PFRST$ in a square $Q$, and then the second player places another n-point set $\PSCND$ into $Q$. The payoff for the second player is the fraction of the area of $Q$ occupied by the regions of the points of $\PSCND$ in the Voronoi diagram of $\PFRST\cup\PSCND$. We give a strategy for the second player that always guarantees him a payoff of at least $\frac12+\alpha$, for a constant $\alpha>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.

REFERENCES

• 1: Hee-Kap Ahn , Siu-Wing Cheng , Otfried Cheong , Mordecai J. Golin , René van Oostrum, Competitive Facility Location along a Highway, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.237-246, August 20-23, 2001
• 2: H. Eiselt and G. Laporte. Competitive spatial models. European Journal of Operational Research, 39:231--242, 1989.
• 3: H. Eiselt, G. Laporte, and J.-F. Thisse. Competitive location models: A framework and bibliography. Transportation Science, 27:44--54, 1993.
• 4: Terry L. Friesz , Roger L. Tobin , Tan Miller, Existence theory for spatially competitive network facility location models, Annals of Operations Research, v.18 n.1-4, p.267-276, Feb. 1989 [doi>10.1007/BF02097808]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Theory

Keywords:
Voronoi diagram, Voronoi game, competitive facility location