The Voronoi Game

This is a game for two players (Dark and Pastel) representing big fast food chains. Alternate building restaurants of your chain in the square shaped city by clicking on it. Under the assumption that each customer (point in the square) visits only the nearest restaurant (no matter from which chain), the task is to maximize the area of customers for your chain. You can change the number of rounds (restaurants in each chain) between 1 and 18. Note that the second player (pastel) has slightly better chances (why?). This game is not fully analyzed yet, except in the one round case, (C. Cheong, S. Har-Peled, N. Linial, J. Matousek, The one-round Voronoi game, in: Proc. 18th Annual Symp. on Computational Geometry, 2002, pp. 97-101.)

By the way, the resulting pictures with the cell of influence for each restaurant is called a Voronoi diagram.

Variant:Again the two players place restaurants alternately. But now the area is irrelevant, instead "Dark"'s aim is to get a connected area of dark influence from the top line to the bottom line of the square, whereas "Pastel" has to create a connected Pastel area from left to right. Each player has to achieve her aim right after clicking. Note that both aims cannot be achieved simultaneously (why?). Is necessarily one achieved at any time?

Erich Prisner, December 2003