Voronoi neighbors: optimization, variation and games

Abstract

Recently several researchers have formulated the competitive facility location problem through Voronoi diagrams where a new site is placed in such a location that its Voronoi region is maximized. One notable result gives a randomized approximation algorithm that works in general settings and another gives a deterministic algorithm that only works in very restricted settings. Research is also going on to find winning strategies for Voronoi games based on area maximization. So far, winning strategies could be found for 1 round games in 2D and for n round games in ID. This thesis addresses cooperative facility location which can be modeled through Voronoi neighborships. We developed a solution which, given n points in 2D, finds the location where a new site should be placed so that it gets the maximum or the minimum number of the existing sites as its neighbors. We also developed a solution to the problem of finding the optimum number of new sites that need to be added to get all existing sites as neighbors. We analyzed optimal playing strategies for a game where the basic objective is' to acquire more neighbors than the opponent. Several variations of the game were considered and we gave winning strategies for some variations, for some variations we showed that it always ends in a tie, and for other variations we showed that the game ends in a tie unless a player plays non-optimally. We also developed an algorithm to generate the arrangement of Delaunay circles in 0 (n) time, and detect all intersections of circles within two Voronoi layers.