Geometry

Japanese polygon theorem

Posted on by John

Here’s an interesting theorem that leads to some aesthetically pleasing images. It’s known as the Japanese cyclic polygon theorem.

For all triangulations of a cyclic polygon, the sum of inradii of the triangles is constant. Conversely, if the sum of inradii is independent of the triangulation, then the polygon is cyclic.

The image above shows two triangulations of an irregular hexagon. By the end of the post we’ll see the code that created these images, and we’ll see one more triangulations. And we’ll see that the sum of the radii of the circles is the same in each image.

Glossary

In case any of the terms in the theorem above are unfamiliar, here’s a quick glossary.

A triangulation of a polygon is a way to divide the polygon into triangles, with the restriction that the triangle vertices come from the polygon vertices.

A polygon is cyclic if there exists a circle that passes through all of its vertices. Incidentally, if a polygon has n + 2 sides, the number of possible triangulations is the nth Catalan number. More on that here.

The inradius of a triangle is the radius of the largest circle that fits inside the triangle. More on inner and outer radii here.

Equations for inradius and incenter

We’d like to illustrate the theorem by drawing some images and by adding up the inradii. This means we need to be able to find the inradius and the incenter.

The inradius of a triangle equals its area divided by its semiperimeter. The area we can find using Heron’s formula. The semiperimeter is half the perimeter.

The incenter is the weighted sum of the vertices, weighted by the lengths of the opposite sides, and normalized. If the vertices are A, B, and C, then the incenter is

\frac{aA + bB + cC}{a + b + c}

where A is the vertex opposite side a, B is the vertex opposite side b, and C is the vertex opposite side c.

Python code

The following Python code will draw a triangle with its incircle. Calling this function for each triangle in the triangulation will create the illustrations we’re after.

from numpy import *
import matplotlib.pyplot as plt

def draw_triangle_with_incircle(A, B, C):
    a = linalg.norm(B - C)
    b = linalg.norm(A - C)
    c = linalg.norm(A - B)
    s = (a + b + c)/2
    r = sqrt(s*(s-a)*(s-b)*(s-c))/s
    center = (a*A + b*B + c*C)/(a + b + c)
    plt.plot([A[0], B[0]], [A[1], B[1]], color="C0")
    plt.plot([B[0], C[0]], [B[1], C[1]], color="C0")
    plt.plot([A[0], C[0]], [A[1], C[1]], color="C0")
    t = linspace(0, 2*pi)
    plt.plot(cos(t) + center[0], sin(t) + center[1], color="C2")
    return r

Next, we pick six points not quite evenly spaced around a circle.

angle = [0, 50, 110, 160, 220, 315] # degrees
p = [array([cos(deg2rad(angle[i])), sin(deg2rad(angle[i]))]) for i in range(6)]

Now we draw three different triangulations of the hexagon defined by the points above. We also print the sum of the inradii to verify that each sum is the same.

def draw_polygon(triangles):
    rsum = 0
    for t in triangles:
        rsum += draw_triangle_with_incircle(p[t[0]], p[t[1]], p[t[2]])        
    print(rsum)
    plt.axis("off")
    plt.gca().set_aspect("equal")
    plt.show()

draw_polygon([[0,1,2], [0,2,3], [0,3,4], [0,4,5]])
draw_polygon([[0,1,2], [2,3,4], [4,5,0], [0,2,4]])
draw_polygon([[0,1,2], [0,2,3], [0,3,5], [3,4,5]])

This produces the two images at the top of the post the one below. All the inradii sum are 1.1441361217691244 with a little variation in the last decimal place.

 

Related posts

Tetrahedral analog of the Pythagorean theorem

Posted on by John

A tetrahedron has four triangular faces. Suppose three of those faces come together like the corner of a cube, each perpendicular to the other. Let A1, A2, and A3 be the areas of the three triangles that meet at this corner and let A0 be the area of remaining face, the one opposite the right corner.

De Gua’s theorem, published in 1783, says

A0² = A1² + A2² + A3².

We will illustrate De Gua’s theorem using Python.

from numpy import *

def area(p1, p2, p3):
    return 0.5*abs(linalg.norm(cross(p1 - p3, p2 - p3)))

p0 = array([ 0, 0,  0])
p1 = array([11, 0,  0])
p2 = array([ 0, 3,  0])
p3 = array([ 0, 0, 25])

A0 = area(p1, p2, p3)
A1 = area(p0, p2, p3)
A2 = area(p0, p1, p3)
A3 = area(p0, p1, p2)

print(A0**2 - A1**2 - A2**2 - A3**2)

This prints 0, as expected.

Higher dimensions

A natural question is whether De Gua’s theorem generalizes to higher dimensions, and indeed it does.

Suppose you have a 4-simplex where one corner fits in the corner of a hypercube. The 4-simplex has 5 vertices. If you leave out any vertex, the remaining 4 points determine a tetrahedron. Let V0 be the volume of the tetrahedron formed by leaving out the vertex at the corner of the hypercube, and let V1, V2, V3, and V4 be the volumes of the tetrahedra formed by dropping out each of the other vertices. Then

V0² = V1² + V2² + V3² + V4².

You can extend the theorem to even higher dimensions analogously.

Let’s illustrate the theorem for the 4-simplex in Python. The volume of a tetrahedron can be computed as

V = det(G)1/2/6

where G is the Gram matrix computed in the code below.

def volume(p1, p2, p3, p4):
    u = p1 - p4
    v = p2 - p4
    w = p3 - p4

    # construct the Gram matrix
    G = array( [
            [dot(u, u), dot(u, v), dot(u, w)],
            [dot(v, u), dot(v, v), dot(v, w)],
            [dot(w, u), dot(w, v), dot(w, w)] ])

    return sqrt(linalg.det(G))/6

p0 = array([ 0, 0,  0, 0])
p1 = array([11, 0,  0, 0])
p2 = array([ 0, 3,  0, 0])
p3 = array([ 0, 0, 25, 0])
p4 = array([ 0, 0,  0, 7])

V0 = volume(p1, p2, p3, p4)
V1 = volume(p0, p2, p3, p4)
V2 = volume(p0, p1, p3, p4)
V3 = volume(p0, p1, p2, p4)
V4 = volume(p0, p1, p2, p3)

print(V0**2 - V1**2 - V2**2 - V3**2 - V4**2)

This prints -9.458744898438454e-11. The result is 0, modulo the limitations of floating point arithmetic.

Numerical analysis

Floating point arithmetic is generally accurate to 15 decimal places. Why is the numerical error above relatively large? The loss of precision is the usual suspect: subtracting nearly equal numbers. We have

V0 = 130978.7777777778

and

V1**2 + V2**2 + V3**2 + V4**2 = 130978.7777777779

Both results are correct to 16 decimal places, but when we subtract them we lose all precision.

Cross ratio

Posted on by John

The cross ratio of four points A, B, C, D is defined by

(A, B; C, D) = \frac{AC \cdot BD}{BC \cdot AD}

where XY denotes the length of the line segment from X to Y.

The idea of a cross ratio goes back at least as far as Pappus of Alexandria (c. 290 – c. 350 AD). Numerous theorems from geometry are stated in terms of the cross ratio. For example, the cross ratio of four points is unchanged under a projective transformation.

Complex numbers

The cross ratio of four (extended [1]) complex numbers is defined by

(z_1, z_2; z_3, z_4) = \frac{(z_3 - z_1)(z_4 - z_2)}{(z_3 - z_2)(z_4 - z_1)}

The absolute value of the complex cross ratio is the cross ratio of the four numbers as points in a plane.

The cross ratio is invariant under Möbius transformations, i.e. if T is any Möbius transformation, then

(T(z_1), T(z_2); T(z_3), T(z_4)) = (z_1, z_2; z_3, z_4)

This is connected to the invariance of the cross ratio in geometry: Möbius transformations are projective transformations on a complex projective line. (More on that here.)

If we fix the first three arguments but leave the last argument variable, then

T(z) = (z_1, z_2; z_3, z) = \frac{(z_3 - z_1)(z - z_2)}{(z_3 - z_2)(z - z_1)}

is the unique Möbius transformation mapping z1, z2, and z3 to ∞, 0, and 1 respectively.

The anharmonic group

Suppose (a, b; c, d) = λ ≠ 1. Then there are 4! = 24 permutations of the arguments and 6 corresponding cross ratios:

\lambda, \frac{1}{\lambda}, 1 - \lambda, \frac{1}{1 - \lambda}, \frac{\lambda - 1}{\lambda}, \frac{\lambda}{\lambda - 1}

Viewed as functions of λ, these six functions form a group, generated by

\begin{align*} f(\lambda) &= \frac{1}{\lambda} \\ g(\lambda) &= 1 - \lambda \end{align*}

This group is called the anharmonic group. Four numbers are said to be in harmonic relation if their cross ratio is 1, so the requirement that λ ≠ 1 says that the four numbers are anharmonic.

The six elements of the group can be written as

\begin{align*} f(\lambda) &= \frac{1}{\lambda} \\ g(\lambda) &= 1 - \lambda \\ f(f(\lambda)) &= g(g(\lambda) = z \\ f(g(\lambda)) &= \frac{1}{\lambda - 1} \\ g(f(\lambda)) &= \frac{\lambda - 1}{\lambda} \\ f(g(f(\lambda))) &= g(f(g(\lambda))) = \frac{\lambda}{\lambda - 1} \end{align*}

Hypergeometric transformations

When I was looking at the six possible cross ratios for permutations of the arguments, I thought about where I’d seen them before: the linear transformation formulas for hypergeometric functions. These are, for example, equations 15.3.3 through 15.3.9 in A&S. They relate the hypergeometric function F(a, b; c; z) to similar functions where the argument z is replaced with one of the elements of the anharmonic group.

I’ve written about these transformations before here. For example,

F(a, b; c; z) = (1-z)^{-a} F\left(a, c-b; c; \frac{z}{z-1} \right)

There are deep relationships between hypergeometric functions and projective geometry, so I assume there’s an elegant explanation for the similarity between the transformation formulas and the anharmonic group, though I can’t say right now what it is.

Related posts

[1] For completeness we need to include a point at infinity. If one of the z equals ∞ then the terms involving ∞ are dropped from the definition of the cross ratio.

An ancient generalization of the Pythagorean theorem

Posted on by John

Apollonius of Perga (c. 262 BC – c. 190 BC) discovered a theorem that generalizes the Pythagorean theorem but isn’t nearly as well known.

Let ABC be a general triangle, and let D be the midpoint of the segment AB. Let a be the length of the side opposite A and b the length of the side opposite B. Let m be the length of AD and h the length of the mediant, the line CD.

Apollonius’s theorem says

a² + b² = 2(m² + h²).

To see that this is a generalization of the Pythagorean theorem, apply Apollonius’ theorem to an isosceles triangle. Now a = b and ACD is a right triangle.

Apollonius’ theorem says

2b² = 2m² + 2h²

which is the Pythagorean theorem applied to ACD with each term doubled.

Random samples from a tetrahedron

Posted on by John

Exactly one month ago I wrote about sampling points from a triangle. This post will look at the three dimensional analog, sampling from a tetrahedron. The generalization to higher dimensions works as well.

Sampling from a triangle

In the triangle post, I showed that a naive approach doesn’t work but a variation does. If the vertices of the triangle are A, B, and C, then the naive approach is to generate three uniform random numbers, normalize them, and use them to form a linear combination of the vertices. That is, generate

r1, r2, r3

uniformly from [0, 1], then define

r1′ = r1/(r1 + r2 + r3)
r2′ = r2/(r1 + r2 + r3)
r3′ = r3/(r1 + r2 + r3)

and return as a random sample the point

r1′ A + r2′ B + r3′ C.

This oversamples points near the middle of the triangle and undersamples points near the vertices. But everything above works if you replace uniform samples with exponential samples.

Sampling from a tetrahedron

The analogous method works for a tetrahedron with vertices A, B, C, and D. Generate exponential random variables ri for i = 1, 2, 3, 4. Then normalize, defining each ri′ to be ri divided by the sum of all the ri s. Then the random sample is

r1′ A + r2′ B + r3′ C + r4′ D.

In the case of the triangle, it was easy to visualize that uniformly generated rs did not lead to uniform samples of the triangle, but that exponentially generated rs did. This is harder to do in three dimensions. Even if the points were uniformly sampled from a tetrahedron, they might not look uniformly distributed from a given perspective.

So how might we demonstrate that our method works? One approach would be to take a cube inside a tetrahedron and show that the proportion of samples that land inside the cube is what we’d expect, namely the ratio of the volume of the cube to the volume of the tetrahedron.

This brings up a couple interesting subproblems.

  1. How do we compute the volume of a tetrahedron?
  2. How can we test whether our cube lies entirely within the tetrahedron?

Volume of a tetrahedron

To find the volume of a tetrahedron, form a matrix M whose columns are the vectors from three of the vertices to the remaining vertex. So we could take A − D, B − D, and C − D. The volume of the tetrahedron is the determinant of M divided by 6.

Testing whether a cube is inside a tetrahedron

A tetrahedron is convex, and so the line segment joining any two points inside the tetrahedron lies entirely inside the tetrahedron. It follows that if all the vertices of a cube are inside the a tetrahedron, the entire cube is inside.

So this brings us to the problem of testing whether a point is inside a tetrahedron. We can do this by converting the coordinates of the point to barycentric coordinates, then testing whether all the coordinates are non-negative and add to 1.

Random sampling illustration

I made up four points as vertices of a tetrahedron.

import numpy as np

A = [0, 0, 0]
B = [5, 0, 0]
C = [0, 7, 0]
D = [0, 1, 6]
A, B, C, D = map(np.array, [A, B, C, D])

For my test cube I chose the cube whose vertex coordinates are all combinations of 1 and 2. So the vertex nearest the origin is (1, 1, 1) and the vertex furthest from the origin is (2, 2, 2). You can verify that all the vertices are inside the tetrahedron, and so the cube is inside the tetrahedron.

The tetrahedron has volume 35, and the cube has volume 1, so we expect 1/35th of the random points to land inside the cube. Here’s the code to sample the tetrahedron and calculate the proportion of points that land in the cube.

from scipy.stats import expon

def incube(v):
    return 1 <= v[0] <= 2 and 1 <= v[1] <= 2 and 1 <= v[2] <= 2

def good_sample(A, B, C, D):
    r = expon.rvs(size=4)
    r /= sum(r)
    return r[0]*A + r[1]*B + r[2]*C + r[3]*D

def bad_sample(A, B, C, D):
    r = np.random.random(size=4)
    r /= sum(r)
    return r[0]*A + r[1]*B + r[2]*C + r[3]*D

N = 1_000_000

badcount  = 0
goodcount = 0

for _ in range(N):
    v = bad_sample(A, B, C, D)
    if incube(v):
        badcount += 1        
    v = good_sample(A, B, C, D)
    if incube(v):
        goodcount += 1

print(badcount/N, goodcount/N, 1/35)

This produced

0.094388 0.028372 0.028571…

The good (exponential) method match the expected proportion to three decimal places but the bad (uniform) method put about 3.3 times as many points in the cube as expected.

Note that three decimal agreement is about what we’d expect via the central limit theorem since 1/√N = 0.001.

If you’re porting the sampler above to an environment where you don’t a function for generating exponential random samples, you can roll your own by returning −log(u) where u is a uniform sample from [0. 1].

More general 3D regions

After writing the post about sampling from triangles, I wrote a followup post about sampling from polygons. In a nutshell, divide your polygon into triangles, then randomly select a triangle in proportion to its area, then sample with that triangle. You can do the analogous process in three dimensions by dividing a general volume into tetrahedra.

Conway’s pinwheel tiling

Posted on by John

John Conway discovered a right triangle that can be partitioned into five similar triangles. The sides are in proportion 1 : 2 : √5.

You can make a larger similar triangle by making the entire triangle the central (green) triangle of a new triangle.

Here’s the same image with the small triangles filled in as in the original.

Repeating this process creates an aperiodic tiling of the plane.

The tiling was discovered by Conway, but Charles Radin was the first to describe it in a publication [1]. Radin attributes the tiling to Conway.

Alternate visualization

It would be easiest to illustrate the tiling if we were standing together in a room and placing new triangles on the floor, watching the tiling expand. Given the limitations of a screen, it may be easier to visualize subdividing the triangle rather than tiling the plane.

Imagine the smallest triangles are a constant size and at each step we’re viewing the process from further away. We see a constant size outer triangle at each step, but the triangle is growing and covering the plane.

Here’s an animated GIF of the process.

 

Related posts

[1] Charles Radin. “The Pinwheel Tilings of the Plane.” Annals of Mathematics, vol. 139, no. 3, 1994, pp. 661–702.

More triangle inequalities

Posted on by John

Yesterday I wrote about a triangle inequality discovered by Paul Erdős.

Let P be a point inside a triangle ABC. Let x, y, z be the distances from P to the vertices and let p, q, r, be the distances to the sides. Then Erdős’ inequality says

x + y + z ≥ 2(p + q + r).

Using the same notation, here are four more triangle inequalities discovered by Oppenheim [1].

  • px + qy + rz ≥ 2(qr + rp + pq)
  • yz + zx + xy ≥ 4(qr + rp + pq),
  • xyz ≥ 8pqr
  • 1/p+ 1/q + 1/r ≥ 2(1/x + 1/y + 1/z)

[1] A. Oppenheim. The Erdös Inequality and Other Inequalities for a Triangle. The American Mathematical Monthly. Vol. 68, No. 3 (Mar., 1961), pp. 226–230

Random samples from a polygon

Posted on by John

Ted Dunning left a comment on my post on random sampling from a triangle saying you could extend this to sampling from a polygon by dividing the polygon into triangles, and selecting a triangle each time with probability proportional to the triangle’s area.

To illustrate this, let’s start with a irregular pentagon.

To pick a point inside, I used the centroid, the average of the vertices. Connecting the centroid to each of the vertices splits the pentagon into triangles. (Here I implicitly used the fact that this pentagon is convex. The centroid of a non-convex polygon could be outside the polygon.)

We can find the area of the triangles using Heron’s rule.

Here’s what we get for random samples.

A triangle inequality by Erdős

Posted on by John

Plane geometry has been studied since ancient times, and yet new results keep being discovered millennia later, including elegant results. It’s easy to come up with a new result by proving a complicated theorem that Euclid would not have cared about. It’s more impressive to come up with a new theorem that Euclid would have understood and found interesting.

Paul Erdős conjectured another triangle inequality in 1935 which was proved by Mordell and Barrow in 1937 [1].

Let P be a point inside a triangle ABC. Let x, y, z be the distances from P to the vertices and let p, q, r, be the distances to the sides. Then

x + y + z ≥ 2(p + q + r)

with equality only if P is the center of an equilateral triangle [2]. In the figure above, the theorem says the dashed blue lines together are more than twice as long as the solid red lines.

How far apart are the left and right sides of the inequality? This was the motivation for the previous post on selecting random points from a triangle. I wanted to generate random points and compare the two sides of the Erdős-Mordell-Barrow inequality.

We can visualize the inequality by generating random points inside the triangle and plotting the points with a color that indicates the inequality gap, darker blue corresponding to a larger gap.

This shows the inequality is sharper in the middle of the triangle than near the vertices.

[1] Problem 3740, American Mathematical Monthly, 44 (1937) 252-254.

[2] You could interpret this as a theorem comparing barycentric and trilinear coordinates.

Intuition for Pick’s Theorem

Posted on by John

Pick’s theorem is a surprising and useful to find the area of a region formed by connecting dots on a grid. The area is simply

A = i + p/2 − 1

where i is the number of dots in the interior and p is the number of dots on the perimeter.

Example

For example, the in the figure below there are 11 black dots on the perimeter and 17 blue dots in the interior.

Therefore Pick’s theorem says the area of the figure is 17 + 11/2 − 1 =  21½.

Intuition

It makes sense that the area would be approximately i if the figure is very large. But why do you need to add half the dots on the perimeter and why do you subtract 1?

Pick’s theorem is simple, but it isn’t obvious. If it were obvious, someone closer to the time of Descartes (1596–1650) would have discovered it. Instead, the theorem was discovered by Georg Alexander Pick in 1899. However, the theorem is fairly obvious for a rectangle, and this post will illustrate that case. For a rectangle, you can easily see why you need to add half the perimeter dots and subtract 1.

Rectangular case

Imagine an m by n rectangular array of dots. If you were to draw a frame around those dots with the corners of the rectangle being exactly between dots, the area would be mn, the number of dots inside the frame.

Pick’s theorem does not apply here because the corners of our frame do not lie on the grid. So let’s shift our grid down and to the left so that its corners do lie on the grid.

Now some of our original dots, marked in blue, are on the perimeter of the frame. We could add the number of dots on the perimeter to correct for this, but that would be too much because the blue dots on the perimeter are only on the left and top sides. Each has a reflection on the right and bottom, marked with red dots. So we shouldn’t add all the dots on the perimeter, but only half the dots on the perimeter.

But that still overcounts slightly. There are two dots on the perimeter that do not correspond to a blue dot or to the reflection of a blue dot. These are the hollow circles in the top right and bottom left corners. So when we take half the perimeter, we need to subtract 1 to account for half of this pair of dots.

This doesn’t prove Pick’s theorem in general, but it does prove it for rectangular regions. Even if we can’t see why the formula generalizes to more complicated regions, we can be grateful that it does.

Related posts