1
$\begingroup$

Wikipedia Delaunay Triangulation

On this page, I read (with $n$ the number of edges): "In the plane (d = 2), 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"

I do understand what the Euler characteristic is about and why they speak about the exterior face, but I can't see how they obtained this result.

I tried to write : $2 = n - V + F$ and $F = 2 - n + V$ but I don't know how to find the number of vertices $V$.

Any help and hints will be greatly appreciated.

$\endgroup$
2
$\begingroup$

According to wikipedia $n$ is the number of vertices.

Suppose you go consider all of the edges of the graph, each time you consider an edge you touch the two faces with which that edge is adjacent. Then each face is going to be touched three times (the triangles) except for the outermost face which is going to be touched $b$ times. Since we touched $2E$ times but also $3(F-1)+b$ times we conclude $2E=3(F-1)+b\implies E=\frac{3(F-1)+b}{2}$

Now write the euler characteristic $n+F-E=2$, substitute $E$ and get $n+F-\frac{3(F-1)+b}{2}=2\implies 2n+2F-3F+3-b=4\implies 2n-1-b=F$.

Therefore the number of faces is $2n-1-b$ implying there are $2n-2-b$ triangles and one exterior face with $b$ edges.

$\endgroup$

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.