Modeling the Competitive Facility Location Problem in a Symmetric Arena

In this paper, we consider the competitive facility location problem as a version of n-round Manhatan-metric Voronoi game with two players, where the distance measure is the Man- hattan metric. Players alternate placing points, one at a time, into the playing arena that is a symmetric polygon, until each of them has placed n points. The arena is then subdivided according to the nearest-neighbor rule under the Manhattan distance, and the player whose points control the larger area wins. We study a winning strategy for the second player in a special version of the game.

Keywords:

Computational geometry , Voronoi diagram , Voronoi game , Game theory , Competitive facility location