Wikipedia on Delaunay Triangulation says:

"In the plane[...], if there are b vertices on the convex hull, then any 
triangulation of the points has at most 2n − 2 − b triangles, plus one 
exterior face."

Here n is the total number of vertices in the plane.

I can't see how they obtained this result when I use Euler's formula 1=V-E+F. So V=n then F=1-n+E. what is face exterior?

  • $\begingroup$ Outside the convex hull, to infinity. $\endgroup$ – Yves Daoust Nov 20 '16 at 11:12
  • $\begingroup$ I don't understand. $\endgroup$ – cripto Nov 20 '16 at 11:17

The exterior face is the green area.

enter image description here

  • $\begingroup$ how do I derive the formula 2n − 2 − b? $\endgroup$ – cripto Nov 20 '16 at 11:36
  • $\begingroup$ @cripto: what are $V,F,E$ ? $\endgroup$ – Yves Daoust Nov 20 '16 at 11:40
  • $\begingroup$ V=vertex, F=faces and E=edges $\endgroup$ – cripto Nov 20 '16 at 11:43
  • $\begingroup$ @cripto: I was sure you would answer this ! $\endgroup$ – Yves Daoust Nov 20 '16 at 11:48
  • $\begingroup$ I don't known where to use 1=V-E+F $\endgroup$ – cripto Nov 20 '16 at 11:56

Euler's formular for planar graphs with $n$ vertices, $e$ edges and $f$ faces says that $2 = n - e + f$. Note that $f$ includes the outer, unbounded face to infinity, too. So we have $f-1$ triangles and a $b$-gon.

We can assign to each edge two tokens; one for each incident face. The number of tokens can be counted per face, too: $3(f-1)$ for $f-1$ triangles and $b$ for the outer face, so $3 (f-1) + b = 2e$.

Then we have $4 = 2n - 2e + 2f = 2n -f -k + 3$, and hence $f-1 = 2n -2 -b$, which is the number of triangles.


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.