MATHS BITE: Shoelace Theorem

The Shoelace theorem is a useful formula for finding the area of a polygon when we know the coordinates of its vertices. The formula was described by Meister in 1769, and then by Gauss in 1795.

Formula

Let’s suppose that a polygon P has vertices (a1, b1), (a2, b2), …, (an, bn), in clockwise order. Then the area of P is given by

$$\dfrac{1}{2} |(a_1b_2 + a_2b_3 + \cdots + a_nb_1) - (b_1a_2 + b_2a_3 + \cdots + b_na_1)|$$

The name of this theorem comes from the fact that if you were to list the coordinates in a column and mark the pairs to be multiplied, then the image looks like laced-up shoes.

Proof

(Note: this proof is taken from artofproblemsolving.)

Let $\Omega$ be the set of points that belong to the polygon. Then

$$A=\int_{\Omega}\alpha,$$

where $\alpha=dx\wedge dy$.

Note that the volume form $\alpha$ is an exact form since $d\omega=\alpha$, where

$$\omega=\frac{x\,dy}{2}-\frac{y\,dx}{2}.\label{omega}$$

Substitute this in to give us

$$\int_{\Omega}\alpha=\int_{\Omega}d\omega.$$

and then use Stokes’ theorem (a key theorem in vector calculus) to obtain

$$\int_{\Omega}d\omega=\int_{\partial\Omega}\omega.$$

where

$\partial \Omega=\bigcup A(i)$

and $A(i)$ is the line segment from $(x_i,y_i)$ to $(x_{i+1},y_{i+1})$, i.e.  is the boundary of the polygon.

Next we substitute for $\omega$:

$$\sum_{i=1}^n\int_{A(i)}\omega=\frac{1}{2}\sum_{i=1}^n\int_{A(i)}{x\,dy}-{y\,dx}.$$

Parameterising this expression gives us

$$\frac{1}{2}\sum_{i=1}^n\int_0^1{(x_i+(x_{i+1}-x_i)t)(y_{i+1}-y_i)}-{(y_i+(y_{i+1}-y_i)t)(x_{i+1}-x_i)\,dt}.$$

Then, by integrating this we obtain

$$\frac{1}{2}\sum_{i=1}^n\frac{1}{2}[(x_i+x_{i+1})(y_{i+1}-y_i)- (y_{i}+y_{i+1})(x_{i+1}-x_i)].$$

This then yields, after further manipulation, the shoelace formula:

$$\frac{1}{2}\sum_{i=1}^n(x_iy_{i+1}-x_{i+1}y_i).$$

M x

Stirling’s Formula

Today I wanted to discuss something I learnt last week in my Probability course: Stirling’s Formula. Stirling’s Formula is an approximation for factorials, and leads to quite accurate results even for small values of n.

The formula can be written in two ways:

or

where the ~ sign means that the two quantities are asymptotic (i.e. their ratios tend to 1 as n tends to infinity).

Comparison of Factorial with Stirling’s Approximation | Source: Wikipedia

Proof of Stirling’s Formula

The following identity arises using integration by parts:

Taking f(x) = log x, we obtain

Next, sum over n, and by recalling that log x + log y = log xy we get the following expression:

where

Next, define

which allows us to rearrange the above expression to:

So as n tends to infinity we get

(*)

How do we show that  ?

Firstly, note that from (*) it follows that

So, we need to show that

Let’s set

Note that I0=π/2 and I1 = 1. Then for n≥2, we can integrate by parts to see that

And so, we obtain the following two expressions:

In is decreasing in n and In/In-2 → 1, so it follows that I2n/I2n+1 → 1. Therefore,

as required.

Although the end result is satisfying, I find that some steps in this proof are like ‘pulling-a-rabbit-out-of-a-hat’! What do you think? Mx