#

#
Voronoi Game

#
Dennis Shasha

#
Omniheurist Course

#
Computer Science

##
*
Description
*

Given a set of point-sized
stones (which we will call ``stones'' for simplicity),
a Voronoi diagram is a tesselation of a plane into polygons
such (i) that every stone is in the interior of one polygon and (ii) for
every point x in the polygon P associated with stone s,
x is closer to s than it is to any other stone s'.
Distance is based on Euclidean distance.

The Voronoi game is a two person game that works as follows:
you and I each start with 7 stones (should be a command line
parameter throughout
-- no magic numbers in your programs please).
Yours are red and mine are blue.
The first player places one stone, then the second player places one stone
and play alternates with each player placing one stone until
the second player places the last stone.

As the game proceeds,
the Voronoi diagram is computed with red polygons surrounding
red stones and blue polygons surrounding blue stones.
The display should make the stones darker than the other points in the polygon.

It may help you to see this by looking at
Chris Poultney's implementation
.

Your job is to find a strategy to play this game competitively.
You may find the following papers useful:

The One-Round Voronoi Game

The one-round Voronoi game replayed
.

The Voronoi game played by people.

* Crispy's current thinking (fall, 2003):*
I think the best strategy involves a blend of offense (greedy algorithms
that net the biggest polygon, like splitting the opponent's biggest
polygon) and defense (dividing your own area into roughly equal-sized
polygons to protect yourself against big losses). I think the stablest
arrangement of points is roughly in a circle with one point in the middle,
with each polygon having a roughly equal area; however, I'm not sure how
this relates to actual game play.