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.

Additional Metadata
Keywords Competitive facility location problem, Geodesic center of a simple polygon, Voronoi game
Persistent URL dx.doi.org/10.1016/j.tcs.2019.04.012
Journal Theoretical Computer Science
Citation
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