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 here. 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:

Downloads

VoronoiGame.jar	Download
Source Code	Download
My thesis (Italian)	View
Indrit Selimi CV

Selected References

Articles

[1] AHN H.K., CHENG S.W., CHEONG O., GOLIN M., OOSTRUM R.V.
Competitive Facility Location along a Highway, 9th Annual International Computing and Combinatorics Conference, Vol. 2108, pages 237-246, 2001.

[2] CHEONG O., LINAL N., HAR-PELED S., MATOUSEK J.
The One-Round Voronoi Game, 18th Annual ACM Symposium on Computational Geometry, pages 97-101, 2002.

[3] FEKETE S.P., MEIJER H.
The One-Round Voronoi Game Replayed, Workshop on Algorithms and Data Structures. Springer Lecture Notes in Computer Science, vol.2748, pages 150-161, 2003.

[4]  CHEONG O., EFRAT A., HAR-PELED S.
On Finding a Guard that Sees Most and a Shop that Sells Most, Symposium on Discrete Algorithms. Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, Session 12B, pages 1098-1107, 2004, ISBN: 0-89871-XXX-X.

[5] DEHNE F., KLEIN R., SEIDEL R.
Maximizing a Voronoi Region: The Convex Case, International Journal of Computational Geometry & Applications, Vol. 15, No. 5, June 16, 2005, pages 463-475.

[6] TERAMOTO S., DEMAINE E., UEHARA R.
Voronoi game on graphs and its complexity, Proceedings of the 2nd IEEE Symposium on Computational Intelligence and Games (CIG 2006), Reno, Nevada, May 22-24, 2006, pages 265-271.

[7]  ZHAO J., STEIGER W.
Remarks on the Voronoi Game, September 23, 2006

[8]  DURR C, KIM THANG N.
Nash equilibria in Voronoi games on graphs, February 2007

[9]  DZIUBINSKI M., DATTA D., ROY J.
A Location Game on Disjoint Circles, Lancaster University Management School Working Paper, July 2007. This paper extends Ahn's et al. [1] results to the multiple disjoint closed curves.

[10]  DZIUBINSKI M.
Voronoi game on disjoint open curves, Lancaster University Management School Working Paper, 2008.
This paper extends Ahn's et al. [1] results to the multiple disjoint open curves.

[11]  MUHIBUR R., MASUD H., M. SOHEL R.
Maximum neighbour Voronoi games, 3rd Annual Workshop on Algorithms and Computations, Indian Statistical Institute, Febrary 2008

[12]  MAVRONICOLAS M., MONIEN B., PAPADOPOULOU V.G., SCHOPPMANN F.
Voronoi Games on Cycle Graphs, Proceedings of the 33rd international symposium on Mathematical Foundations of Computer Science, 2008

Other Articles

CHAWLA S., RAJAN U., RAVI R., SINHA A.
Worst-Case Payoffs of a Location Game, Carnegie Mellon University

LAW J. A., JOHNSON J. H.
The Voronoi Game in Robot Coordination,Proceedings of the FIRA RoboWorld Congress, Dortmund, Germany, June 2006.

JAGER G.
Convex meanings and evolutionary stability, Proceedings of the 6th International Conference on the Evolution of Language, pages 139-144, 2006

YINGCHAO Z., WEI C., SHANG-HUA T.
The Isolation Game: A Game of Distances, September 2008

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.