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?


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.

| cite | improve this answer | |
  • $\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$ – 今天春天 May 22 '16 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 May 23 '16 at 6:05
  • $\begingroup$ What if I want to have a Voronoi Diagram with exactly one vertex? $\endgroup$ – 今天春天 May 23 '16 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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