Upper-bound on the number of edges in the farthest-point voronoi diagram

computational geometrygeometryvoronoi diagram

I'm trying to prove that the number of edges in the farthest-point voronoi diagram of $n$ points is upper-bounded by $2n-3$ (as claimed by Computational Geometry: Algorithms and Applications). I could only show that $3n – 6$ is an upper bound (not as strict as required), as follows:

I follow the notation below:

  • $v$ is the number of vertices in the farthest-point voronoi diagram
  • $e$ is the number of edges in the farthest-point voronoi diagram
  • $f$ is the number of faces in the farthest-point voronoi diagram

Now I show the following:

  1. By adding a new vertex $v_{\infty}$, and connecting all of the diagram's unbounded edges to it, we create a connected planar graph with $v+1$ vertices and the same number of edges and faces.
  2. Since now the planar graph is connected, every vertex has a degree of at least 3. Therefore, $2e \geq 3(v + 1)$.
  3. Since only points on the convex hull of the $n$-points set have a cell in the farthest-point voronoi diagram, we get that $f \leq n$.
  4. Plugging #2 and #3 into Euler's $(v + 1) – e + f = 2$ yields that $e \leq 3n – 6$

This is actually the same upper bound on the number of edges in the closest-point voronoi diagram.
What do I miss in order to get the tighter bound ($2n-3$) for the farthest-point voronoi diagram?
I guess I need to use the tree structure of the diagram, but I don't see how.

farthest point voronoi diagram

Best Answer

Denote by $m$ the extremal points of the convex hulls of the $n$ sites/points. Your third observation can be re-stated as $f=m\le n$. My advice would be to try to obtain a bound on $v$ with respect to $m$, instead of comparing $v$ and $e$.

One way to do that is as follows:

Hint 1:

Take a look at the dual to the furthest-point Voronoi diagram, it is a triangulation of the convex hull.

Hint 2:

By definition of the dual, each triangle of the triangle correspond to a vertex in the Voronoi diagram. So you can express $v$ by expressing the number of triangles $t$ in the dual ($v=t$).

Hint 3:

$v=t=m-2$.

Hint 4:

Plug hint 3 and your observation 3 into $(v+1)-e+f=2$... and remember that $m\le n$.

Related Question