One-Round Discrete Voronoi Game in R2 in Presence of Existing Facilities

In this paper we consider a simplified variant of the dis-crete Voronoi Game in R2, which is also of independent interest in competitive facility location. The game con-sists of two players P1 and P2, and a finite set U of users in the plane. The players have already placed two sets of facilities F and S, respectively in the plane. The game begins by P1 placing a new facility followed by P2 placing another facility, and the objective of both the players is to maximize their own total payoffs. When |F | = |S | = m, this corresponds to the last round of the (m + 1)-round discrete Voronoi Game in R2. In this paper we propose polynomial time algorithms for obtaining optimal strategies of both the players under arbitrary locations of the existing facilities F and S. We show that the optimal strategy of P2, given any place-ment of P1, can be found in O(n2) time, and the optimal strategy of P1 can be found in O(n8) time.