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 ;-)

  • $\begingroup$ Thanks for the amazing insight. $\endgroup$ – rizwanhudda Apr 28 '12 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.