Prove that there is a set of $n$ points such that a Voronoi cell contains $n-1$ vertices. We need to prove the following claim:

There exists a set of $n$ points such that a Voronoi cell of one of the points contains $n-1$ vertices.

I think in the following case the Voronoi cell for point $C$ contains $n-1$ vertices, but I'm unable to prove it.

$ P = \{ p_1, p_2,p_3,..,p_{n-1} \} \cup \{ C \} $
$S = \{p_i : 1 \leq i \leq n -1 \}$ are vertices of regular convex polygon and $C$ is its centre.

 A: I am assuming that you are talking about Voronoi cells on a plane with standard metric. I also guess that "cell contains $n-1$ vertices" means "the cell is a polygon which boundary has at least $n-1$ vertices".
Unfortunately theorem fails for $n = 2$ and $n = 3$ (unless you put a vertex in infinity). For $n \geq 4$ you are right. To prove that is suffices to show the following:


*

*The cell of $C$ is bounded.

*All the others cells are its neighbors.


(1) is trivial for $n \geq 4$. To show (2) just consider a segment from $C$ to some of $p_i$ and some other $p_j$. Let $X$ be the midpoint of $Cp_i$, then by the triangle inequality and $|Cp_i| = |Cp_j|$ and $p_i \neq p_j$ we have that $|XC| = |Xp_i| < |Xp_j|$ so there exists a small ball where $C$ and $p_i$ are the only possible candidates for the closest vertex are $C$ and $p_i$ (just put a center at $X$ and take $r = \frac{\min_j|Xp_j|-|Xp_i|}{2}$). But $|XC| = |Xp_i|$ so cells of $C$ and $p_i$ share an edge of length greater or equal $2r$.
With (1) and (2) you can show that the cell of $C$ has at least $n-1$ edges and that it is bounded, i.e. each edge is a segment, which means that the boundary must have at least $n-1$ vertices and this concludes the proof.
Hope this helps ;-)
