Voronoi Diagrams Proof

Question

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?

Answer 1

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.

Answer 2

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.