In this paper we consider a competitive facility location problem played between two players P1 and P2. Let P be a simple polygon with m vertices. Consider a set of users, U modeled as points in the interior (excluding the boundary) of P. Initially P1 chooses a point inside P (including the boundary) to place a facility. Following this P2 chooses another point inside P and places a facility. Given these facilities a user u∈U is served by its nearest facility, where distances are measured by the geodesic distance in P. The objective of each player is to maximize the number of users they serve. We show that for any given placement of a facility by P1, an optimal placement for P2 can be computed in O(m+n(log⁡n+log⁡m)) time. We also provide a polynomial-time algorithm for computing an optimal placement for P1.

, ,
Theoretical Computer Science
Computational Geometry Lab

Banik, A. (Aritra), Das, S. (Sandip), Maheshwari, A, & Smid, M. (2019). The discrete Voronoi game in a simple polygon. Theoretical Computer Science. doi:10.1016/j.tcs.2019.04.012