Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks for the amazing insight. –  rizwanhudda Apr 28 '12 at 17:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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