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.

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?

share|improve this question
    
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

2 Answers 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$.

enter image description here

Since $r$ is unbounded and contained in $V(p_i)$, $V(p_i)$ is unbounded.

share|improve this answer

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.

share|improve this answer

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.