# Voronoi Diagrams Proof

I am having a real problem with this proof about voronoi diagrams:

Prove that $V(p_i)$ (i.e., the cell of $\operatorname{Vor}(P)$ which corresponds to $p_i$) is unbounded if and only if $p_i$ is on the convex hull of the point set, $P = \{p_1,p_2,\ldots,p_n\}$.

Can anyone offer some assistance?

-
Do you have a reference to the proof you are studying? – M.B. Nov 15 '12 at 19:25
And what do you know about the underlying metric space? – M.B. Nov 15 '12 at 19:30
This might be from my textbook. Sounds familiar... – Joseph O'Rourke Nov 15 '12 at 21:02

Take a supporting line $s$ of $\text{conv}(P)$ running through $p_i$. Then consider the ray $r$ emanating from $p_i$ that is orthogonal to $s$ and points away from $\text{conv}(P)$. Every point $x$ on this ray has $p_i$ as closest point of $P$. To see this consider the circle around $x$ that touches $p_i$, this circle is tangent to $s$ and therefore intersects $\text{conv}(P)$ only in $p_i$.
Since $r$ is unbounded and contained in $V(p_i)$, $V(p_i)$ is unbounded.
I suggest you leverage the corresponding Delaunay triangulation for your proof. Every triangle of the Delaunay triangulation corresponds to a vertex of your Voronoi cells. Points on the convex hull are exactly those points which are not surrounded by Delaunay triangles. More precisely, a point lies on the convex hull iff every $\varepsilon$ neighbourhood contains points not belonging to any Delaunay triangle. Which means that there are directions in which the cell extends infinitely.