Voronoi games and epsilon nets
Competitive facility location is concerned with the strategic placement of facilities by competing market players. In the Discrete Voronoi Game V G(k; l), two players P1 and P2, respectively, strive to attract as many of n users as possible. Initially, P1 first chooses a set F of k locations in the plane to place its facilities. Then, P2 chooses a set S of l locations in the plane to place its facilities, where S ∩ F = Ø. Finally, the users choose the facilities based on the nearest-neighbour rule. The goal for each player is to maximize the number of users served by its set of facilities. By establishing a connection between V G(2; 1) and ε-nets, we provide an algorithm running in O(n log4 n) time to find a 7/4 -factor approximation of the optimal strategy of P1 in V G(2; 1). We also prove that for any real number 0 < α < 1, there exists a placement of 42/α facilities by P1 such that P2 can serve at most αn users by placing one facility.
|Conference||26th Canadian Conference on Computational Geometry, CCCG 2014|
Banik, A. (Aritra), De Carufel, J.-L. (Jean-Lou), Maheshwari, A, & Smid, M. (2014). Voronoi games and epsilon nets. Presented at the 26th Canadian Conference on Computational Geometry, CCCG 2014.