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.

Additional Metadata
Conference 26th Canadian Conference on Computational Geometry, CCCG 2014
Citation
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.