  The one-round discrete Voronoi game, with respect to a $n$-point user set
$U$, consists of two players Player 1 ($\mathcal{P}_1$) and Player 2
($\mathcal{P}_2$). At first, $\mathcal{P}_1$ chooses a set of facilities $F_1$
following which $\mathcal{P}_2$ chooses another set of facilities $F_2$,
disjoint from $F_1$. The payoff of $\mathcal{P}_2$ is defined as the
cardinality of the set of points in $U$ which are closer to a facility in $F_2$
than to every facility in $F_1$, and the payoff of $\mathcal{P}_1$ is the
difference between the number of users in $U$ and the payoff of
$\mathcal{P}_2$. 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 $\mathcal{P}_1$ places $k$ facilities and $\mathcal{P}_2$ places one
facility and we have denoted this game as $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)$ with significantly better running times. We provide a constant-factor
approximate solution to the optimal strategy of $\mathcal{P}_1$ in $VG(k,1)$ by
establishing a connection between $VG(k,1)$ and weak $\epsilon$-nets. To the
best of our knowledge, this is the first time that Voronoi games are studied
from the point of view of $\epsilon$-nets.
