An n-gon (which is not self-intersecting) is triangulated using m interior vertices. In other words, there is a set of N triangles such that: (1) their union is the original n-gon; (2) the union of their vertices is the set consisting of the n vertices of the n-gon and the m interior vertices; (3) the intersection of any two distinct triangles in the set is either empty, a vertex of both triangles, or a side of both triangles. What is N?
Solution
Answer: N = n + 2m - 2.
We use the well-known relation F = E + 2 - V (*), where F is the number of faces, E the number of edges and V the number of vertices. In this case, F = N + 1, because there are N triangles and one n-gon (the exterior polygon). So 3N + 1.n gives each edge twice, in other words 2E = 3N + n. Clearly V = m + n. So (*) gives: N + 1 =3N/2 + n/2 + 2 - m - n. Hence N = n + 2m - 2.
© John Scholes
jscholes@kalva.demon.co.uk
14 Jan 2002