The Voronoi Game

The Voronoi Game is a simple geometric model for the competitive facility location. Competitive facility location studies the placement of sites by competing market players. The geometric concepts are combined with game theory arguments to study if there exists any winning strategy. The Voronoi Game is a direct application of Voronoi Diagrams which are some kind of graphs embedded on the plane. To understand what's the Voronoi Diagram of a set of points (the latests in this context are called sites) in the plane we must think about the two sites scenario. In this case the Voronoi Diagram is represented by the bisector relative of the two sites on the plane. The bisector is the locus of points in the plane at equal distance from the two sites thereby it determinate two regions constituted by points that are at a closer distance to one of the sites than the other. This concept may be generalized for the case of n sites in someway because the bisector concept continues to apply in a certain point of view. More formally defined a metric on the plane, a point q will be within the corresponding cell of the site pi if and only if the distance between q and pi is smaller than between q and any other site in the plane. There will be always a region for every site containing the points that are closer to the respective site then to all the other sites. This distance propriety is used in the Voronoi game for modelling competitive players in a determined arena.

Voronoi Game Origins

The first implementation of the Voronoi game was written by Chris Poultney and Monty Faidley as a class final project in 1996, you can try it . The Ahn[1] paper with its nice analysis of the game acknowledges Dr. Ecco which is a mathematical detective about whom Prof. Dennis Shasha has written several books. The Voronoi game appears as a puzzle in the book Codes, Puzzles, and Conspiracy in 1992 (after republished as Dr.Ecco: mathematical detective), where it is called the Territory Game and is inspired by the Falklands War.

What's the Voronoi Game?

Voronoi game is played in its basic version by two players (Blue & Red) that insert in alternated mode a certain number n of points. The scenario is divided by calculating the Voronoi Diagram relative to the points inserted and finally the winner is the player that has occupied the greatest area at the moment when all the points from both players are inserted. There is another version in which the players insert their points in single shoot, for this reason the game in this case is called "One Round Voronoi Game". The question is: Is there a strategy that allows one of the players to win? At a first glance one may think that because of the symmetry involved it's impossible to synthesize a winning strategy but this turned to be not true. We are speaking of "area" but there exist Voronoi Diagrams defined in multiple dimensions spaces therefore there will be a Voronoi Game for the one-dimensional case. Ahn (who coined the term Voronoi Game) et al. [1] were the firsts to demonstrate that there exists a winning strategy for the one dimensional arena case i.e., a line segment [0, 1]. They were able to define a strategy based on certain key positions called keypoints in which the first player (Blue) must occupy in order to win the game, however in this case the second player (Red) can keep its loosing margin arbitrarily small. The latest assertion implies that in all practical situations the Voronoi Game in one dimensional case ends in a tie. What's for the two dimensional case? Cheong et al. [2] showed that the dimensional scenario differs significantly. They showed that for sufficiently large number of sites n > n* the second player (Red) has a winning strategy that guarantees at least a fixed fraction of 1/2 + epsilon of the total area. Finally Fekete and Meijer [3] studied the following issues:

• How large does n* have to be to guarantee a winning for the Red player and if there exists multiple values of n that cause one of the player to win?

• In which manner the aspect ratio of the game arena affects the outcome of the game?

For rectangular boards with an aspect ratio r <1 they prove the following:

• The second player has a winning strategy for n >= 3 and r > 2½ / n, and for n = 2 and r > 3½ / 2. The first player wins in all remaining cases, i.e., for n >= 3 and r <= 2½ / n, for n = 2 and r <= 3½/2, and for n = 1.

• If the first player does not play his points on an orthogonal grid, then the second player wins the game.

The Voronoi Game Applet

I have written a java program that implements the Voronoi Game. The java program may run both as an applet or an application. The java version required is 1.4.1 or higher, visit the java.com if you want to download the latest java virtual machine. Here you may play the game online pushing the respective image at the end of this paragraph or simply pushing here. The source code is supplied with the GNU General Public License and you have to follow the rules imposed by this license. I will be thankful to those who will suggest me any improvement or advice for the code. I would like to see code improvements by yourself also. To view game instructions you must launch the applet and consult the help on-line. If more in-depth information is needed you may write to me or you may view my thesis(only in Italian) in PDF format at the bottom of this page. It is possible to play off-line downloading the Jar file that contains the bytecodes and the source code. For Windows users just double click the downloaded file to launch the voronoi game. For others systems you may consult this page for instructions. Enjoy the Voronoi Game!

To play the Voronoi Game you may push here or on the beneath image:

Selected References

Articles

Other Articles

Web sites

Geometry in Action
A very useful web site focused on discrete and computational geometry with a lot of links to other web resources.

The Voronoi Web Site
Contains a very useful list of links about voronoi diagrams and more.

Last Updated: 12 December 2008