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.
