|
|
|
|
|
|
|
|
|
Diagonal CountThe purpose of this page is to help you count a number of non-intersecting diagonals in a convex polygon. I won't give you the formula right away. You are to come up with the right one by experimenting with the applet below. Once you surmise the right result, try to prove it before looking into the explanation at the bottom of the page. To draw diagonals just drag the mouse from one vertex to another. Remember that you are counting non-intersecting diagonals.
ExplanationIt's obvious that from a given vertex one may only draw exactly (n-3) diagonals. For one can't draw a diagonal to the selected vertex itself and its two immediate neighbors. Such diagonals will not intersect one another. What's interesting is that, in a convex n-gon, the number of non-intersecting diagonals always equals (n-3) regardless of which diagonals are drawn and in what order. Proof #1After all eligible diagonals have been drawn, the polygon will be split into a number T of triangles. Between them these triangles have 3T sides. Except that those that coincide with diagonals are counted twice. Let D be the number of diagonals. We thus have
Adding up interior angles of the triangles gives, on the one hand, 180oT = 180o(n + 2D)/3. On the other hand, since diagonals do not intersect, their angles fill up the angles of the polygon. Thus (by the distributive law),
Simplifying we get D = n - 3. As a byproduct of the proof, we obtain a formula for the number of triangles thus formed: T = (n + 2(n-3))/3 = n - 2. Proof #2 (By induction)For n = 3 D = 0 since a triangle has no diagonals. Assume the formula has been established for all m<n. Consider a convex n-gon and draw its diagonals as expected. We may cut the polygon along one of its diagonals which will create two smaller polygons with their diagonals drawn according the conditions of our theorem. For, if we could draw an additional diagonal in one of the polygons, this line would serve as a diagonal in the original one as well. "Non-intersection" condition will also be inherited which would contradict our construction. Let the two polygons have n1 and n2 sides, respectively. Then n1 + n2 = n + 2; for the selected diagonal will be counted as a side of both small polygons. In obvious notations, D1 = n1 - 3 and D2 = n2 - 3 by the inductive assumption. On the other hand, D1 + D2 = D - 1; for the selected diagonal drops out of the count. Combining these two facts leads to
and finally to the desired result. Note that since both n1,n2 Remark 1If we are looking for the totality of all diagonals in an n-gon allowing for intersections then, of course, it does not matter in what order we count them - there is a unique set of all diagonals of a given polygon. From any of the n vertices emanate (n-3) diagonals which gives n(n-3) except that each diagonal, having two ends, is counted twice. Therefore the total number of diagonals in an n-gon is n(n-3)/2. Remark 2The question of a number of ways in which a convex (n+2)-gon can be split into n triangles (Euler's problem) leads to the famous Catalan numbers
Catalan numbers pop up in a multitude of seemingly unrelated places. M. Gardner reports that in 1976 Henry. W. Gould counted 450 references. Popular acounts can be found in
|
3,
n1 + n2 = n + 2 implies n1,n2<n as needed.
| 29436902 |  |
|