0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Outside the convex hull, to infinity. $\endgroup$
    – user65203
    Nov 20, 2016 at 11:12
  • $\begingroup$ I don't understand. $\endgroup$
    – Tommy
    Nov 20, 2016 at 11:17

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

The exterior face is the green area.

enter image description here

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .