Content area
Full Text
Discrete Comput Geom 31:125138 (2004) Discrete & ComputationalDOI: 10.1007/s00454-003-2951-4Otfried Cheong,1 Sariel Har-Peled,2 Nathan Linial,3 and Jir Matousek41Department of Mathematics and Computer Science, Eindhoven University of Technology,
P.O. Box 513, 5600 MB Eindhoven, The [email protected] of Computer Science, University of Illinois,
1304 W. Springfield Ave., Urbana, IL 61801, USA
[email protected] of Computer Science, Hebrew University,Jerusalem 91904, [email protected] of Applied Mathematics andInstitute of Theoretical Computer Science (ITI), Charles University,
Malostranske nam. 25, 118 00 Praha 1, Czech Republic
[email protected]. 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 leastGeometry 2003 Springer-Verlag New York Inc.The One-Round Voronoi Game, 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 than1
2+ 1
2 .1. IntroductionCompetitive facility location studies the placement of sites by competing market players.
Overviews of different models are the surveys by Tobin et al. [9], Eiselt and Laporte [3],
and Eiselt et al. [4]. Part of this research was done during a workshop supported by ITI (Project LN00A056 of the Ministry of
Education of the Czech Republic). N.L. was supported in part by a grant from the Israel Science Foundation.126 O. Cheong, S. Har-Peled, N. Linial, and J. MatousekThe Voronoi game is a simple geometric model for competitive facility location, where
a site s owns the part of the playing arena that is closer to s than to any other site. We
consider a two-player version with a square arena Q. The two players, White and Black,
place points into Q. As in chess, White plays first. The goal of both players is to capture
as much of the area of Q as possible, where the region captured by White isR(W, B) ={x Q: dist(x, W)< dist(x, B)}and the region captured by Black is R(B, W). Here W is the...