Maximum Neighbour Voronoi Games

摘要

Recently several researchers have studied the competitive facility location problem in the form of Voronoi games, where each of the two players places n points with the target of maximizing total Voronoi area of its sites in the Voronoi diagram of 2n points. In this paper we address this problem by introducing Voronoi games by neighbours where the basic objective of an optimal playing strategy is to acquire more neighbors than the opponent. We consider several variations of this game, and for each variation we either give a winning strategy, if it exists, or show how the game ends in a tie.