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

作者：Banik Aritra; De Carufel Jean Lou^*; Maheshwari Anil; Smid Michiel

来源：Computational Geometry-Theory and Applications, 2016, 55: 41-58.

DOI：10.1016/j.comgeo.2016.02.002

• Voronoi games
• Facility location
• epsilon-Nets
• Minimum k-enclosing disk

The one-round discrete Voronoi game, with respect to an n-point user set U, consists of two players Player 1 (P-1) and Player 2 (P-2). At first, P-1 chooses a set of facilities F-1 following which P-2 chooses another set of facilities F-2, disjoint from F-1. The payoff of 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 P-1 is the difference between the number of users in U and the payoff of 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 P-1 places k facilities and P-2 places one facility. We denote this game as VG(k, I). 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 P1 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.

• 出版日期2016-5