How many ways can you triangulate a regular polygon?

Posted on 16 April 2025 by John

In this post we want to count the number of ways to divide a regular polygon [1] into triangles by connecting vertices with straight lines that do not cross.

Squares

For a square, there are two possibilities: we either connect the NW and SE corners,

or we connect the SW and NE corners.

Pentagons

For a pentagon, we pick one vertex and connect it to both non-adjacent vertices.

We can do this for any vertex, so there are five possible triangulations. All five triangulations are rotations of the same triangulation. What if we consider these rotations as equivalent? We’ll get to that later.

Hexagons

For a hexagon, things are more interesting. We can again pick any vertex and connect it to all non-adjacent vertices, giving six triangulations.

But there are more possibilities. We could connect every other vertex, creating an equilateral triangle inside. We can do this two ways, connecting either the even-numbered vertices or the odd-numbered vertices. Either triangulation is a rotation of the other.

We can also connect the vertices in a zig-zag pattern, creating an N-shaped pattern inside. We could also rotate this triangulation one or two turns. (Three turns gives us the same pattern again.)

Finally, we could also connect the vertices creating a backward N pattern.

General case

So to recap, we have 2 ways to triangulate a square, 5 ways to triangulate a pentagon, and 6 + 2 + 3 + 3 = 14 ways to triangulate a hexagon. Also, there is only 1 way to triangulate a triangle: do nothing.

Let C_n be the number of ways to triangulate a regular (n + 2)-gon. Then we have C₁ = 1, C₂ = 2, C₃ = 5, and C₄ = 14.

In general,

$C_n = \frac{1}{n+1}\binom{2n}{n}$

which is the nth Catalan number.

Catalan numbers are the answers to a large number of questions. For example, C_n is also the number of ways to fully parenthesize a product of n + 1 terms, and the number of full binary trees with n + 1 nodes.

The Catalan numbers have been very well studied, and we know that asymptotically

$C \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}$

so we can estimate C_n for large n. For example, we could use the formula above to estimate the number of ways to triangulate a 100-gon to be 5.84 ×10⁵⁵. The 98th Catalan number is closer to 5.77 ×10⁵⁵. Two takeaways: Catalan numbers grow very quickly, and we can estimate them within an order of magnitude using the asymptotic formula.

Equivalence classes

Now let’s go back and count the number of triangulations again, considering some variations on a triangulation to be the same triangulation.

We’ll consider rotations of the same triangulation to count only once. So, for example, we’ll say there is only one triangulation of a pentagon and four triangulations of a hexagon. If we consider mirror images to be the same triangulation, then there are three triangulations of a hexagon, counting the N pattern and the backward N pattern to be the same.

Grouping rotations

The number of equivalence classes of n-gon triangulations, grouping rotations together, is OEIS sequence A001683. Note that the sequence starts at 2.

OEIS gives a formula for this sequence:

$a(n) = \frac{1}{2n}C_{n-2} + \frac{1}{4}C_{n/2-1} + \frac{1}{2} C_{\lceil (n+1)/2\rceil - 2} + \frac{1}{3} C_{n/3 - 1}$
where C_x is zero when x is not an integer. So a(6) = 4, as expected.

Grouping rotations and reflections

The number of equivalence classes of n-gon triangulations, grouping rotations and reflections together, is OEIS sequence A000207. Note that the sequence starts at 3.

OEIS gives a formula for this sequence as well:

$a(n) = \frac{1}{2n}C_{n-2} + \frac{1}{4}C_{n/2-1} + \frac{1}{2} C_{\lceil (n+1)/2\rceil - 2} + \frac{1}{3} C_{n/3 - 1}$

As before, C_x is zero when x is not an integer. This gives a(6) = 3, as expected.

The formula on the OEIS page is a little confusing since it uses C(n) to denote C_n−2 .

[1] Our polygons do not need to be regular, but they do need to be convex.

Erdős-Mordell triangle theorem

Posted on 13 April 2025 by John

If any field of mathematics has been thoroughly combed over, it’s Euclidean geometry. But once in a while someone will come up with a new theorem that seems it should have been discovered centuries ago.

Here’s a theorem conjectured by Paul Erdős in 1935 and proved by Louis Mordell later the same year.

If from a point O inside a given triangle ABC perpendiculars OD, OE, OF are drawn to its sides, then

OA + OB + OC ≥ 2(OD + OE + OF).

Equality holds if and only if triangle ABC is equilateral.

To put it more succinctly,

From any interior point, the distances to the vertices are at least twice the distances to the sides.

Here’s an illustration. In the figure above, the theorem says the dashed blue lines together are more than twice as long as the solid red lines.

In the units I used in drawing the figure above, the blue lines have combined length 9.5 and the red lines have combined length 4.7.

Hojoo Lee gave an elementary proof of the Erdős-Mordell theorem in 2001 that takes about one printed page [1].

In my opinion the Erdős-Mordell theorem feels like a theorem an ancient geometer could have discovered and proved. Here’s a generalization of the theorem that feels much more contemporary [2].

Let R_i be the distance from an interior point O to the ith vertex and r_i the distance to the side opposite the ith vertex. Let λ₁, λ₂, and λ₃ be any three positive real numbers. Then

$\sum_{i=1}^3 \lambda_iR_i \geq 2\sqrt{\lambda_1\lambda_2\lambda_3} \sum_{i=1}^3 \frac{r_i}{\sqrt{\lambda_i}}$

When all the λs equal 1, we get the original Erdős-Mordell theorem.

You could say the weighted distances to the vertices are at least twice the weighted distances to the sides, but you have to say more about the weights, and in general the weights work differently on both sides of the inequality.

[1] Hojoo Lee. Another Proof of the Erdős-Mordell Theorem. Forum Geometricorum, Volume 1 (2001) p. 7–8

[2] Seannie Dar, Shay Gueron. A Weighted Erdős-Mordell Inequality. The American Mathematical Monthly. Vol. 108, No. 2, Feb., 2001

Interior of a conic

Posted on 20 March 2025 by John

What is the interior of a circle? Obvious.

What is the interior of a parabola? Not quite as obvious.

What is the interior of a hyperbola? Not at all obvious.

Is it possible to define interior in a way that applies to all conic sections?

Circles

If you remove a circle from the plane, there are two components left. Which one is the interior and which one is the exterior?

Obviously the bounded part is the interior and the unbounded part is the exterior. But using boundedness as our criteria runs into immediate problems.

Parabolas

If you remove a parabola in the plane, which component is the interior and which is the exterior? You might say there is no interior because both components of the plane minus the parabola are unbounded. Still, if you had to label one of the components the interior, you’d probably say the smaller one.

But is the “smaller” component really smaller? Both components have infinite area. You could patch this up by taking a square centered at the origin and letting its size grow to infinity. The interior of the parabola is the component that has smaller area inside the square all along the way.

Hyperbolas

A hyperbola divides the plane into three regions. Which of these is the interior? If we try to look at area inside an expanding square, it’s not clear which component(s) will have more or less area. Seems like it may depend on the location of the center of the square relative to the position of the hyperbola.

Tangents to a circle

Here’s another way to define the interior of a circle. Look at the set of all lines that are tangent to a point on the circle. None of them go through the interior of the circle. We can define the interior of the circle as the set of points that no tangent line passes through.

This clearly works for a circle, and it’s almost as clear that it would work for an ellipse.

How do we define the exterior of a circle? We could just say it’s the part of the plane that isn’t the interior or the circle itself. But there is a more interesting definition. If the interior of the circle consists of points that tangent lines don’t pass through, the exterior of the circle consists of the set of points that tangent lines do pass thorough. Twice in fact: every point outside the circle is at the intersection of two lines tangent to the circle.

To put it another way, consider the set of all tangent lines to a circle. Every point in the plane is part of zero, one, or two of these lines. The interior of the circle is the set of points that belong to zero tangent lines. The circle is the set of points that belong to one tangent line. The exterior of the circle is the set of points that belong to two tangent lines.

Tangents to a parabola

If we apply the analogous definition to a parabola, the interior of the parabola works out to be the part we’d like to call the interior.

It’s not obvious that every point of the plane not on the parabola and not in the interior lies at the intersection of two tangent lines, but it’s true.

Tangents to a hyperbola

If we look at the hyperbola x² − y² = 1 and draw tangent lines, the interior, the portion of the plane with no crossing tangent lines, is the union of two components, one containing (−∞, −1) and one containing (1, ∞). The exterior is then the component containing the line y = x. In the image above, the pink and lavender components are the interior and the green component is the exterior.

It’s unsatisfying that the interior of the hyperbola is disconnected. Also, I believe the exterior is missing the origin. Both of these annoyances go away when we add points at infinity. In the projective plane, the complement of a conic section consists of two connected components, the interior and the exterior. The origin lies on two tangent lines: one connecting (−∞, −∞) to (∞, ∞) and one connecting (−∞, ∞) to (∞, −∞).

Do perimeter and area determine a triangle?

Posted on 26 February 2025 by John

Is the shape of a triangle determined by its perimeter and area? In other words, if two triangles have the same area and the same perimeter, are the triangles similar? [1]

It’s plausible. A triangle has three degrees of freedom: the lengths of the three sides. Specifying the area and perimeter removes two degrees of freedom. Allowing the triangles to be similar rather than congruent accounts for a third degree of freedom.

Here’s another plausibility argument. Heron’s formula computes the area of a triangle from the lengths of the sides.

$A = \sqrt{s(s-a)(s-b)(s-c)}$

Here s is the semi-perimeter, half of the sum of the lengths of the sides. So if the perimeter and area are known, we have a third order equation for the sides:

$(a - s)(b - s)(c - s) = -\frac{A^2}{s}$

If the right-hand side were 0, then we could solve for the lengths of the sides. But the right-hand side is not zero. Is it still possible that the sides are uniquely determined, up to rearranging how we label the sides?

It turns out the answer is no [2], and yet it is not simple to construct counterexamples. If all the sides of a triangle are rational numbers, it is possible to find a non-congruent triangle with the same perimeter and area, but the process of finding this triangle is a bit complicated.

One example is the triangles with sides (20, 21, 29) and (17, 25, 28). Both have perimeter 70 and area 210. But the former is a right triangle and the latter is not.

Where did our algebraic argument go wrong? How can a cubic equation have two sets of solutions? But we don’t have a cubic equation in one variable; we have an equation in three variables that is the product of three linear terms.

What third piece of information would specify a triangle uniquely? If you knew the perimeter, area, and the length of one side, then the triangle is determined. What if you specified the center of the triangle? There are many ways to define a center of a triangle; would some, along with perimeter and area, uniquely determine a triangle while others would not?

[1] Two triangles are similar if you can transform one into the other by scaling and/or rotation.

[2] Mordechai Ben-Ari. Mathematical Surprises. Springer, 2022. The author sites this blog post as his source.

Area of a quadrilateral from the lengths of its sides

Posted on 19 January 2025 by John

Last week Heron’s formula came up in the post An Unexpected Triangle. Given the lengths of the sides of a triangle, there is a simple expression for the area of the triangle.

$A = \sqrt{s(s-a)(s-b)(s-c)}$

where the sides are a, b, and c and s is the semiperimeter, half the perimeter.

Is there an analogous formula for the area of a quadrilateral? Yes and no. If the quadrilateral is cyclic, meaning there exists a circle going through all four of its vertices, then Brahmagupta’s formula for the area of a quadrilateral is a direct generalization of Heron’s formula for the area of a triangle. If the sides of the cyclic quadrilateral are a, b, c, and d, then the area of the quadrilateral is

$A = \sqrt{(s-a)(s-b)(s-c)(s-d)}$

where again s is the semiperimeter.

But in general, the area of a quadrilateral is not determined by the length of its sides alone. There is a more general expression, Bretschneider’s formula, that expresses the area of a general quadrilateral in terms of the lengths of its sides and the sum of two opposite angles. (Either pair of opposite angles lead to the same value.)

$A = \sqrt {(s-a)(s-b)(s-c)(s-d) - abcd \, \cos^2 \left(\frac{\alpha + \gamma}{2}\right)}$

In a cyclic quadrilateral, the opposite angles α and γ add up to π, and so the cosine term drops out.

The contrast between the triangle and the quadrilateral touches on an area of math called distance geometry. At first this term may sound redundant. Isn’t geometry all about distances? Well, no. It is also about angles. Distance geometry seeks results, like Heron’s theorem, that only depend on distances.

The mathematics of GPS

Posted on 16 November 2024 by John

The basic idea of GPS is that if you know the distance to several satellites, you can figure out your position. But you don’t actually know, or need to know, the distance to the satellites: you know the time (according to each satellite’s clock) when the signals were sent, and you know the time (according to your clock) when the signals arrived.

The atomic clocks on satellites are synchronized with each other to within a nanosecond, but they’re not synchronized with your clock. There is some offset t between your clock and the satellites’ clocks. Presumably t is small, but it matters.

If you observe m satellites, you have a system of m equations in 4 unknowns:

|| a_i − x || = t_i − t

where a_i is the known position of the ith satellite in 3 dimensions, x is the observer’s position in three dimensions, and t_i is the difference between the time when the signal left the ith satellite (according to its clock) and the time when the signal arrived (according to the observer’s clock). This assumes we choose units so that the speed of light is c = 1.

So we have a system of m equations in 4 unknowns. It’s plausible there could be a unique solution provided m = 4. However, this is not guaranteed.

Here’s an example to suggest why there may not be a unique solution. Suppose t is known to be 0. Then observing 3 satellites will give us 3 equations in 3 unknowns. Each t_i determines a sphere of radius t_i. Suppose two spheres intersect in a circle, and the third sphere intersects this circle in two points. This means we have two solutions to our system of equations.

In [1] the authors thoroughly study the solution to the GPS system of equations. They allow the satellites and the observer to be anywhere in space and look for conditions under which the system has a unique solution. In practice, GPS satellites are approximately confined to a sphere (more on that here) and the observer is also approximately confined to a sphere, namely the earth’s surface, but the authors do not take advantage of these assumptions.

The authors also assume the problem is formulated in n dimensional space, where n does not necessarily equal 3. It’s complicated to state when the system of equations has a unique solution, but allowing n to vary does not add to the complexity.

I’m curious whether there are practical uses for the GPS problem when n > 3. There are numerous practical problems involving the intersections of spheres in higher dimensions, where the dimensions are not Euclidean spacial dimensions but rather abstract degrees of freedom. But off hand I cannot think of a problem that would involve the time offset that GPS location finding has.

[1] Mireille Boutin, Gregor Kemperc. Global positioning: The uniqueness question and a new solution method. Advances in Applied Mathematics 160 (2024)

Triangle circle maximization problem

Posted on 16 October 2024 by John

Let a, b, and c be the sides of a triangle. Let r be the radius of an inscribed circle and R the radius of a circumscribed circle. Finally, let p be the perimeter. Then the previous post said that

2prR = abc.

We could rewrite this as

2rR = abc / (a + b + c)

The right hand side is maximized when a = b = c. To prove this, maximize abc subject to the constraint a + b + c = p using Lagrange multipliers. This says

[bc, ac, ab] = λ[1, 1, 1]

and so ab = bc = ac, and from there we conclude a = b = c. This means among triangles with any given perimeter, the product of the inner and outer radii is maximized for an equilateral triangle.

The inner radius for an equilateral triangle is (√3 / 6)a and the outer radius is a/√3, so the maximum product is a²/6.

Relating six properties of a triangle in one equation

Posted on 15 October 2024 by John

Triangle with inscribed and circumscribed circles

Let a, b, and c be the sides of a triangle.

Let p be perimeter of the triangle.

Let r be the radius of the largest circle that can be inscribed in the triangle, and let R be the radius of the circle through the vertices of the triangle.

Then all six numbers can be related in one equation:

2prR = abc.

Triangles to Triangles

Posted on 11 October 2024 by John

The set of functions of the form

f(z) = (az + b)/(cz + d)

with ad ≠ bc are called bilinear transformations or Möbius transformations. These functions have three degrees of freedom—there are four parameters, but multiplying all parameters by a constant defines the same function—and so you can uniquely determine such a function by picking three points and specifying where they go.

Here’s an explicit formula for the Möbius transformation that takes z₁, z₂, and z₃ to w₁, w₂, and w₃.

$\begin{vmatrix} 1 & z & w & zw \\ 1 & z_1 & w_1 & z_1w_1 \\ 1 & z_2 & w_2 & z_2w_2 \\ 1 & z_3 & w_3 & z_3w_3 \\ \end{vmatrix} = 0$

To see that this is correct, or at least possible, note that if you set z = z_i and w = w_i for some i then two rows of the matrix are equal and so the determinant is zero.

Triangles, lines, and circles

You can pick three points in one complex plane, the z-plane, and three points in another complex plane, the w-plane, and find a Möbius transformation w = f(z) taking the z-plane to the w-plane sending the specified z‘s to the specified w‘s.

If you view the three points as vertices of a triangle, you’re specifying that one triangle gets mapped to another triangle. However, the sides of your triangle may or may not be straight lines.

Möbius transformations map circles and lines to circles and lines, but a circle might become a line or vice versa. So the straight lines of our original triangle may map to straight lines or they may become circular arcs. How can you tell whether the image of a side of a triangle will be straight or curved?

When does a line map to a line?

It’ll be easier if we add a point ∞ to the complex plane and think of lines as infinitely big circles, circles that pass through ∞.

The Möbius transformation (az + b)/(cz + d) takes ∞ to a/c and it takes −d/c to ∞.

The sides of a triangle are line segments. If we look at the entire line, not just the segment, then this line is mapped to a circle. If this line contains the point that gets mapped to ∞ then the image of the line is an infinite circle (i.e. a line). Otherwise the image of the line is a finite circle.

The line between z₁ and z₂ can be parameterized by

z₁ + t(z₂ − z₁)

where t is real. So the image of this line will be a line if and only if

z₁ + t(z₂ − z₁) = −d/c

for some real t. So solve for t and see whether you get a real number.

Note that if the point that is mapped to ∞ lies inside the line segment, not just on the line, then the image of that side of the triangle is infinitely long.

Examples

To keep things as simple as possible without being trivial, we’ll use the Möbius transformation f(z) = 1/z. Clearly the origin is the point that is mapped to ∞. The side of a triangle is mapped to a straight line if and only if the side is part of a line through the origin.

First let’s look at the triangle with vertices at (1, 1), (1, 4), and (5, 1). None of the sides is on a line that extends to the origin, so all sides map to circular arcs.

Next let’s move the second point from (1, 4) to (4, 4). The line running between (1, 1) and (4, 4) goes through the origin, and so the segment along that line maps to a straight line.

Golden ellipse

Posted on 10 October 2024 by John

A golden ellipse is an ellipse whose axes are in golden proportion. That is, the ratio of the major axis length to the minor axis length is the golden ratio φ = (1 + √5)/2.

Draw a golden ellipse and its inscribed and circumscribed circles. In other words draw the largest circle that can fit inside and the smallest circle outside that contains the ellipse.

Then the area of the ellipse equals the area of the annulus bounded by the two circles. That is, the area of the green region

equals the area of the orange region.

The proof is straight forward. Let a be the semimajor axis and b the semiminor axis, with a = φb.

Then the area of the annulus is

π(a² − b²) = πb²(φ² − 1).

The area of the ellipse is

πab = πφb².

The result follows because the golden ratio satisfies

φ² − 1 = φ.

Geometry

How many ways can you triangulate a regular polygon?

Squares

Pentagons

Hexagons

General case

Equivalence classes

Grouping rotations

Grouping rotations and reflections

Related posts

Erdős-Mordell triangle theorem

Interior of a conic

Circles

Parabolas

Hyperbolas

Tangents to a circle

Tangents to a parabola

Tangents to a hyperbola

Do perimeter and area determine a triangle?

Related posts

Area of a quadrilateral from the lengths of its sides

Related posts

The mathematics of GPS

Triangle circle maximization problem

Related posts

Relating six properties of a triangle in one equation

Triangles to Triangles

Triangles, lines, and circles

When does a line map to a line?

Examples

Related posts

Golden ellipse

Related posts