Research On Voronoi Game Of Competitive Facility Location Problem

In this paper, we study the minimum neighbor-getting problem and Maximum neighbor Voronoi game.The minimum neighbor-getting problem is defined as follows:given a set of n points in the plane, the objective is to place k new sites in the plane such that all of n sites can be got as neighbors by new sites in the resulting Delaunay triangulation of n+k points, making k as minimum as possible. The Maximum neighbor Voronoi game is defined as that:There are two Players A and B who need to place sites in the plane. A first places his/her n sites, then B places his/her own n sites. In the resulting Delaunay triangulation of In sites, the player who can get more opponent’s sites as neighbors than the other player wins the game. The objective is to design a strategy for the player to win the game. The problem of finding an optimal way of placing sites is known as Voronoi games and falls in general under the competitive facility location problem.We first consider to place one new site to get three sites which from a Delaunay triangle as neighbors and place one site to get four sites which two adjacent Delaunay triangles as neighbors in local area of the Delaunay triangulation D of n sites. According to these ideas, we can get the locations where the new sites should be placed to solve the minimum neighbor-getting problem by finding a minimum vertex cover and a maximum match of the Voronoi diagram corresponding to D. We give a approximation algorithm to get all n sites as neighbors by at most2n-h-2sites, and a approximation algorithm to get all n sites as neighbors by at most (7n-7-3h)/5sites, where h is the number of sites on the convex hull of the Delaunay triangulation D. We also conduct a high-performance heuristic and it’s improved algorithm. By some experimental verifications of above algorithms, we show that our algorithms can work with better performance than the results given by former researchers under certain conditions.For the maximum neighbor Voronoi game, we give the winning strategy for Player B by using the four algorithms and self-hidding strategy. Then we present a heuristic self-protection strategy for Player A.