A zero-sum game with a maximizer that selects a point x in given polygon R in the plane and a minimizer that selects K points cÅ1,cÅ2,...,cK in the plane is considered; the payoff is the Euclidean distance from x to the closest of the points cj, or any monotonically nondecreasing function of this quantity. Lower and upper bounds on the value of the game are derived by considering, respectively, the maximizer’s strategy of selecting a uniformly distributed random point in R and the minimizer’s strategy of selecting K members of a (uniformly) randomly positioned grid of centers that induce a covering of R by K congruent regular hexagons. The analysis shows that these strategies are asymptotically optimal (for K⇒•). For Euclidean location problems with uniformly distributed customers, the results imply that hexagonal partitioning of the region is asymptotically optimal and that the uniform distribution is asymptotically the worst possible.
