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 voronoi cell of one of the points contains n-1 vertices.

I think in the following case voronoi cell for point C contains n-1 vertices, but 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.

-

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:

1. The cell of $C$ is bounded.
2. 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 ;-)

-
Thanks for the amazing insight. –  rizwanhudda Apr 28 '12 at 17:52