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.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

Explanation

|Contact| |Front page| |Contents| |Eye opener| |Geometry|

Copyright © 1996-2017 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

  3T = n + 2D.

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

  cn = (2n)!/[n!(n+1)!].

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

  1. J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
  2. H.Dorrie, 100 Great Problems Of Elementary Mathematics, Dover Publications, NY, 1965.
  3. M.Gardner, Time Travel and Other Mathematical Bewilderments, W.H.Freeman and Co., NY, 1988.

Related material
Read more...

  • Chessboard
  • Changing Colors, an Interactive Activity
  • Plus or Minus Game
  • Solitaire on a Circle
  • Squares, Circles, and Triangles
  • Calendar Magic
  • Counting Diagonals in a Convex Polygon
  • The Game of Fif
  • Nim
  • |Contact| |Front page| |Contents| |Geometry| |Eye opener| |Up|

    Copyright © 1996-2017 Alexander Bogomolny

     62686486

    Search by google: