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.
In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $Ssubset mathbb{R}^2$ and an angle $0 < theta leq 2pi$, we define the continuous Yao graph $cY(theta)$ with vertex set $S$ and angle $theta$ as follows. For
each $p,qin S$, we add an edge from $p$ to $q$ in $cY(theta)$ if there exists a cone with apex $p$ and aperture $theta$ such that $q$ is the closest point to $p$ inside this cone. We study the spanning ratio of $cY(theta)$ for different values of $theta$. Using a new algebraic technique, we show that $cY(theta)$ is a spanner when $theta leq 2pi /3$. We believe that this technique may be of independent interest. We also show that $cY(pi)$ is not a spanner, and that $cY(theta)$ may be disconnected for $theta > pi$.
