Optimal Strategies for the One-Round Discrete Voronoi Game on a Line

摘要

The one-round discrete Voronoi game, with respect to a n-point user set u, consists of two players Player 1 (PI) and Player 2 (P2). At first, P_1 chooses a set F_1 of m facilities following which P2 chooses another set F_2 of m facilities, disjoint from F_1, where m = 0(1) is a positive constant. The payoff of a player i is defined as the cardinality of the set of points in U which are closer to a point in F_i than to every point in F_j, for i =≠ j. The objective of both the players in the game is to maximize their respective payoffs. In this paper, we address the case where the points in U are located along a line. We show that if the sorted order of the points in U along the line is known, then the optimal strategy of P2, given any placement of facilities by P_1, can be computed in O(n) time. We then prove that for m > 2 the optimal strategy of P_1 in the one-round discrete Voronoi game, with the users on a line, can be computed in O(n~m-λ_m) time, where 0 < λ_m < 1, is a constant depending only on m.