Discrete Voronoi games and ϵ-nets, in two and three dimensions

The one-round discrete Voronoi game, with respect to an n-point user set U  , consists of two players Player 1 (P1P1) and Player 2 (P2P2). At first, P1P1 chooses a set of facilities F1F1 following which P2P2 chooses another set of facilities F2F2, disjoint from F1F1. The payoff of P2P2 is defined as the cardinality of the set of points in U   which are closer to a facility in F2F2 than to every facility in F1F1, and the payoff of P1P1 is the difference between the number of users in U   and the payoff of P2P2. The objective of both the players in the game is to maximize their respective payoffs. In this paper we study the one-round discrete Voronoi game where P1P1 places k   facilities and P2P2 places one facility. We denote this game as VG(k,1)VG(k,1). Although the optimal solution of this game can be found in polynomial time, the polynomial has a very high degree. In this paper, we focus on achieving approximate solutions to VG(k,1)VG(k,1) with significantly better running times. We provide a constant-factor approximate solution to the optimal strategy of P1P1 in VG(k,1)VG(k,1) by establishing a connection between VG(k,1)VG(k,1) and weak ϵ-nets. To the best of our knowledge, this is the first time that Voronoi games are studied from the point of view of ϵ-nets.