Diagonal Count
The 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.
Explanation
|Contact|
|Front page|
|Contents|
|Eye opener|
|Geometry|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
Explanation
It'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 #1
After 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, 180°T = 180°(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),
| |
180°(n - 2) = 180°(n + 2D)/3.
|
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
| |
|
D1 + D2 | = (n1 - 3) + (n2 - 3) |
| | = n1 + n2 - 6 |
| | = (n + 2) - 6 = D - 1 |
|
and finally to the desired result. Note that since both n1,n2≥3,
n1 + n2 = n + 2 implies n1,n2<n as needed.
Remark 1
If 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 2
The 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
- J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
- H.Dorrie, 100 Great Problems Of Elementary Mathematics, Dover Publications, NY, 1965.
- M.Gardner, Time Travel and Other Mathematical Bewilderments, W.H.Freeman and Co., NY, 1988.
|Contact|
|Front page|
|Contents|
|Geometry|
|Eye opener|
|Up|
|Store|
Copyright © 1996-2012 Alexander Bogomolny
|
