# Every triangulation of a finite point set $S$ contains $3|S|-3-h$ edges

In computational geometry, polygon triangulation is the decomposition of a polygonal area (simple polygon) $P$ into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$.

Question : Prove that every triangulation of a finite point set $S$ contains $3|S|-3-h$ edges, where the boundary of $ConvexHull(S)$ contains $h$ edges.

Note : I think the method of proof is induction. But, I don't know which variable i should use for the induction.

• Have you heard about the Euler characteristic? That being said, letting $|S|$ be the induction variable is probably not a bad idea. – Arthur Nov 11 '16 at 11:32
• @Arthur Yeah i know it ... ok, i'm gonna try ... if i failed, i'd edit my question and write more details about my try ... – Arman Malekzadeh Nov 11 '16 at 11:56