I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices.

I tried to use the Euler formula for planar graphs which says $v-e+f = 2$:

$\Rightarrow 2n -5 -e + n = 2 \Rightarrow e = 3n-7$ - but what can I now do with the information that $V(S)$ has $3n-7$ vertices?


1 Answer 1


You made a small mistake by thinking that the Voronoi diagram is a planar graph. Remember that it has those rays that go to infinity. you can make a planar graph out of the Voronoi diagram by adding a new vertex and making all rays incident to this "apex". Plugging this into Euler's formula yields

$$ 2n-4 - e + n = 2 \quad \Rightarrow \quad e= 3n - 6.$$

A planar graph has $3n-6$ edges if it is a triangulation (this can als be obtained via Euler's formula – just set $3f=2e$). As a consequence the dual graph to your Voronoi diagram (the Delaunay tessellation) is a triangulation. Or phrased differently, every vertex of your Voronoi diagram has degree~3 and there are three rays.

  • $\begingroup$ Thank you for this. I want exactly $3n-6$ edges...the definintion of a triangulation says there are $<= 3n-6$ edges. is this a problem? $\endgroup$ Commented May 22, 2016 at 7:56
  • $\begingroup$ Its exactly $3n-6$ edges if the outer face is a triangle (which corresponds to the 3 rays in the Voronoi diagram). $\endgroup$
    – A.Schulz
    Commented May 23, 2016 at 6:05
  • $\begingroup$ What if I want to have a Voronoi Diagram with exactly one vertex? $\endgroup$ Commented May 23, 2016 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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