A (possibly boring) Voronoi Game

Question

The board for this game is a compact convex region $\cal C$ of $\mathbb{R}^2$. Below I illustrate with $\cal C$ an equilateral triangle. Two players, $A$ and $B$, alternate turns. At each turn they add one point in $C$, not closer than $\epsilon > 0$ to any previously placed point. Label the points $a_1, b_2, a_3, b_4, a_5, \ldots$, with the letter indicating the player, and the subscript the turn number. The goal of the game is to control the most area. $A$'s area is the sum of the areas of the Voronoi regions of $a_1, a_3, a_5, \ldots$ within $\cal C$, and $B$'s area is similarly the areas of the Voronoi regions of of $b_2, b_4, b_6, \ldots$.

For example, below $A$ selects $a_1$ to be the centroid of $\cal C$, and $B$ selects $b_2$ to be $\epsilon$ below $a_1$. At this stage, $B$ is winning, owning about $\frac{5}{9}(\sqrt{3}/4) \approx 0.24$ while $A$ owns about $\frac{4}{9}(\sqrt{3}/4) \approx 0.19$. (Let us assume $\epsilon$ is very small.) It seems the next best step for $A$ is to grab most of $B$'s portion by placing $a_3$ just under $b_2$:

---

     

---

Q1. Does optimal (greedy at each step) play result in collinear points separated by $\epsilon$, for all $\cal C$? At least up until an accumulation of $\epsilon$s runs into boundary effects?

Q2. For any $\cal C$, is player $A$ ever ahead (under optimal play) after $B$ has just moved?

Answer 1

I'll give this a try. I certainly have an answer to Q2 and depending on what you mean exactly by boundary effects also an answer to Q1.

Q2. Yes. Take $\mathcal{C}$ as the unit disk. Player $A$ begins by choosing the origin. Then $B$ chooses some point $(b_1,b_2)$. Because of the rotational symmetry, we can assume $b_1=0$, $b_2>0$. Now one sees that $A$ controls the entire semidisk below the $x$-axis as well as a small strip up to the height $b_2/2$ of the upper semidisk. So $A$'s area is bigger.

Q1. No. Consider the same situation as above. We see that minimizing $b_2$ maximizes $B$'s area, so greedy play dictates that $b_2=\epsilon$. If your statement were true, then $A$ would continue by choosing $(0,2\epsilon)$, then $B$ chooses $(0,-\epsilon)$ etc.

Now suppose this has gone on for a while and the region of the disk between $y=-3/4$ and $y=3/4$ has been cut up into strips belonging to $A$ and $B$ respectively. (This certainly constitutes an "accumulation of $\epsilon$s". But we're still far away from the boundary if $\epsilon$ is small! So I'm not sure if this belongs already to what you mean by "boundary effects".)

Player $A$'s last move was to place a point at $(0,-3/4)$ (for simplicity $\epsilon=3/8n$ for some big $n$). If $B$ stays on the line and chooses $(0,-3/4-\epsilon)$ or $(0,3/4+\epsilon)$, she can gain at most around $0.1133...$ area.

But if $B$ chooses $(2/3,0)$, she will control at least the circle of radius 1/3 around this point. This circle has been cut up completely into strips and $A$ controls about half of it. So $B$ can gain about $\pi/18 \approx 0.1745...$ area.

Answer 2

Here's a negative answer to Q1.

Take the unit circle. Say $A$ starts at the origin. Then the first five moves will be in a straight line, symmetric about the origin. I claim the sixth move will not be on that line.

Here is a picture, with epsilon highly exaggerated:

The first five moves are marked in blue and red. $B$ wants to play $\epsilon$ distance away from $A$'s last move, i.e., on the red circle. He could continue the line (at purple), but he would do well to deviate very slightly (pink). The corresponding Voronoi lines are shown. The pink one passes closer to the center of the circle, so it cuts out a larger area. So, in this picture at least, pink is the better move.

If you run the computation, you can see that in a circle, deviating on the sixth move is better no matter what $\epsilon$ is. I'll spare the details because they're a bit hairy, but they work both on paper and on my computer's geometry package.

(Note that $B$ should be careful not to deviate so much that his newly gained area overlaps with his already-owned stripes of area; or so much that when calculating the gained area, he has to worry about any of $A$'s plays except the last one.)