Hi All!
There’s always a plenty of things to do in this period, everybody is for some reason excited with the upcoming end of the year as if that date on that particular calendar had any meaning at all. Additionally I’m at work instead of lazing as most of the people.
Anyway, I got a new book from Santa Claus –delivered by its fellow Zwarte Piet– and a new suit for the sauna.
I’m very happy about this new lecture, I was willing to undertake some study about the machine learning theories long time ago, but didn’t had very much free time for it.
But let’s have a look at the problem I have for today, here’s the statement:
For n>=4 let r(n) denote the number of interior regions of a convex n-gon divided by all its diagonal if no tree diagonal are concurrent within the n-gon, find r(n).
So what we want is to count the regions delimited by all the diagonals of the n-gon, let’s have a look at a more general question in order to understand how to calculate those regions.
Let’s pick a circle and draw in it some chords:
Looks like the amount of regions if we disallow the intersections is equal to the amount of chords plus one, whereas if we allow the intersection then is equal to the amount of chords plus the amount of intersections plus one.
The whole point now is just noticing that we can inscribe a n-gon in a circle and use the very same rule to calculate the number of regions. The whole problem turns out to be all about calculating the diagonals in the n-gon and the amount of intersections –and then applying the rule we found for a circle-, let’s have a look:
The amount diagonals is clearly n(n-3)/2 since we have a diagonal between each point and all the other n-3 points, we halve this value to avoid counting twice the diagonals.
For the amount of intersections, just note that you need four points in order to be able to draw an intersection point between two diagonals, thus nC4. The rest is just the simplification which allows to obtain the formula for r(n)=nC4+(n-1)C2.
Now, this is a very simplified version of a much more complex problem which is about calculating the amount of regions in a regular n-gon, in this case we may have to abandon the condition for which no three points are concurrent, and the rule we have found here are not valid anymore!.
For some details about the math involved you may here a look here, or for the long story short have a look here.
In general there are plenty of similar problems like for example the Euler’s Polygon division problem which turns out to be some flavor of combinatoric problems.
Thanks for reading 🙂