Discrete Voronoi Games and $\epsilon$-Nets, in Two and Three Dimensions

Abstract

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.