Thursday, November 17, 2011

Math Problem: Evenly spaced points on a sphere - Part 3

Continued from Part 2

Let’s try to find a way to systematically divide the triangles on a sphere into smaller triangles in such a way that the resulting triangles are as evenly spaced as possible, starting with either a tetrahedron, an octahedron, or an icosahedron. One thing we can do is place a new point in the center of each triangle. This is called a Kleetope. It is not possible to create a distribution of points that is as evenly spaced as possible by producing successive Kleeptopes because the resulting triangles will become less and less like equilateral triangles. Some points will be very close to each other and other points will be further apart.

original triangle   subdivided once by threes   subdivided twice by threes

Another thing we can do is split each triangle into four triangles by placing new points at the midpoint of each triangle edge.

original triangle   subdivided once by fours   subdivided twice by fours

When you subdivide a triangle into four triangles on the surface of a sphere, the four triangles are not all the same size. The center one is larger. But as you keep subdividing and the triangles get smaller, the curvature of the sphere makes less and less of a difference and the size of the subdivided triangles become more uniform. So if you can show that a set of points after some number of subdivisions are as evenly spaced as possible, then further subdivisions will also be as evenly spaced as possible. Let’s find the size of the center triangle after subdividing.

triangle with labels

Use the spherical law of cosines twice, once for the bigger triangle, and once for the smaller triangle. We’ll assume the radius of the sphere is 1.

cos(x) = cos(a)^2 + sin(a)^2 cos(t)

cos(2 a) = cos(2 a)^2 + sin(2 a)^2 cos(t)

Solve for cos(t).

cos(t) = ( cos(2 a) - cos(2 a)^2 ) / sin(2 a)^2

Try to simplify using the pythagorean trigonometric identity and the double angle formula.

cos(t) =

cos(t) =

Substitute for cos(t) in the smaller triangle.

cos(x) =

cos(x) =

cos(x) =

cos(x) = ( 3 cos(a)^2 - 1 ) / ( 2 cos(a)^2 )

When the big triangle (2 a) is very small, x is barely bigger than a. When 2 a is 2 pi / 9 (or 40°), x is about 5% bigger than a. When 2 a is 4 pi / 9 (or 80°), x is about 24% bigger than a. Finally, when 2 a is 2 pi / 3 (or 120°), x is twice the size of a, which is the same size as the original triangle. This is the case when the three original points are all evenly spaced around the equator, and the three new points are placed on the midpoints, which are also on the equator.

My guess is that you could take a tetrahedron, an octahedron, or an icosahedron, and iteratively split each triangle into four triangles, and you’d end up with an arrangement of points at each iteration that is as evenly spaced as it could be. Additionally, you could form the Kleeptope one time for each of these iterative arrangements and the arrangement of points would be as evenly spaced as they could be.

Iteratively splitting the tetrahedron

pointsedgesfacesdistance between adjacent points
464109.4712°
10241654.7356° and 90°
349664various


Forming the Kleetope for each iteration of the tetrahedron

pointsedgesfacesdistance between adjacent points
81812109.4712° and something
267248various
98288192various


Iteratively splitting the octahedron

pointsedgesfacesdistance between adjacent points
612890°
18483245° and 60°
66192128various


Forming the Kleetope for each iteration of the octahedron

pointsedgesfacesdistance between adjacent points
14362490° and something
5014496various
194576384various


Iteratively splitting the icosahedron

pointsedgesfacesdistance between adjacent points
12302063.435°
421208031.717° and 36°
162480320various


Forming the Kleetope for each iteration of the icosahedron

pointsedgesfacesdistance between adjacent points
32906063.435° and something
122360240various
4821440960various


So it looks like we can make a lot of arrangements of points that are probably as evenly spaced as possible, and we can make them larger and larger without limit.

However, it may not possible to mathematically specify an arrangement of points that is as evenly spaced as possible for any number of points n, because when n is a large prime, the optimal arrangement of points is probably unrelated to any patterns of points for any smaller n.

Sunday, November 13, 2011

Math Problem: Evenly spaced points on a sphere - Part 2

Continued from Part 1

In an ideal case, we would be able to position all the points around the sphere so that they formed equilateral triangles and all the adjacent points were exactly the same difference apart.

I should be more specific about what I mean by adjacent points. Draw a line connecting the two points that are closest to each other. Then draw a line connecting the next two points that are the next closest to each other and where the line wouldn’t cross any other existing lines. Continue along like this until no more lines can be drawn. The points with a line connecting them are considered to be adjacent.

In the ideal case, we can divide the surface area of the sphere by the number of triangles to find the surface area along the sphere of each triangle.

Let’s find the relationship between the number of points, the number of triangle edges, and the number of triangular faces. A tetrahedron has four points, six edges, and four faces. Whenever you add another point that is not in the same spot as an existing point, it will either fall along an existing edge or on a face. In either case, there will be three more edges and two more faces.

points edges faces
4 6 4
5 6+3 4+2
6 6+3+3 4+2+2
n 3 (n - 2) 2 (n - 2)


So in the ideal case, the spherical surface area A of each triangle is

A = (2 pi r^2) / (n-2)

Now let’s find the relationship between the distance 'd' along the surface of the sphere between two adjacent points and the spherical surface area of the triangle anchored by these two points. We can use Girard's theorem to find the relationship between the spherical vertex angle 't' and the spherical surface area A, and we can use the spherical law of cosines to find the relationship between the distance 'd' and the vertex angle 't'.

Use the spherical law of cosines.

Let a = d/r

cos(a) = cos(a)^2 + sin(a)^2 cos(t)

Solve for a.

First use the Pythagorean trigonometric identity to substitute.

cos(a) = cos(a)^2 + (1-cos(a)^2) cos(t)

Group the terms.

(1-cos(t)) cos(a)^2 - cos(a) + cos(t) = 0

Use the quadratic formula.

cos(a) = (1 +- sqrt(1 - 4 (1 - cos(t)) cos(t))) / (2 (1 - cos(t)))

Simplify.

cos(a) = (1 +- sqrt(1 - 4 cos(t) + 4 cos(t)^2)) / (2 (1 - cos(t)))

cos(a) = (1 +- (1 - 2 cos(t))) / (2 (1 - cos(t)))

cos(a) = 1 or cos(t) / (1 - cos(t))

We can ignore the case when cos(a) = 1 because that is when a = 0 or 2 π, which is when the two points are in the same location.

Now use Girard's theorem.

A = (3 t - pi) r^2

Solve for t.

t = (A + pi r^2)/(3 r^2)

Substitute for A.

t = (n pi)/(3 (n - 2))

Now substitute this for t in the equation for cos(a) above.

cos(a) = cos((n pi)/(3 (n - 2))) / (1 - cos((n pi)/(3 (n - 2))s))

In most cases we will not be able to position the points into perfect equilateral triangles of this size because the triangles will start to overlap or leave gaps with each other, but we can do it for n=4 the tetrahedron, n=6 the octahedron, and n=12, the icosahedron.

In the other cases, we can measure the amount of unevenness U by looking at the difference between the ideal distance between adjacent points 'd' and the actual distance between adjacent points dk. Define U as the sum of the squares of these differences:

U = sum( (dk - d)^2 )

For the tetrahedron, octahedron, and icosahedron, U = 0. For the other cases, we will try to position the points so that U is as small as possible.

So the next questions are whether there is a way to systematically position the points to minimize U, and given a configuration of points, how can you tell if U for this configuration is the lowest possible.

You can probably show that U is a local minimum if moving any one point by some small distance delta in any direction causes U to increase, but how do you determine whether that local minimum is the lowest minimum possible?

One way to explore this further is to build a computer simulation of marbles around the surface of a sphere that are all magnetically opposed to each other. Or better yet, let the force between any two adjacent points be proportional to the square of the difference between the actual distance between the points and the ideal distance between the points, so that the points are always being pushed towards the ideal distance.

Continue to Part 3

Saturday, October 29, 2011

Math Problem: Evenly spaced points on a sphere - Part 1

If place points around the circumference of a circle, it is not difficult to position them so that they're evenly spaced.

regular polygons

nangleanglename
32π / 3120°triangle
4π / 290°square
52π / 572°pentagon
n2π / n360 / nn-gon


But suppose you want to position points around the surface of a sphere so that they're evenly spaced.

What is the angle between adjacent points? Is it possible to position the points so that the angle is the same between all adjacent points on the sphere?

Let's look at some examples. For n=4, you have a tetrahedron.
tetrahedron

According to wikipedia, the angle between adjacent points is arccos(-1/3) or about 109.4712°.

For n=6, you have an octahedron. The angle between adjacent points is π / 2 or 90°.

octahedron

To summarize and expand:

nfacestri. facesedgestri. edgesangleanglename
44466arccos(-1/3)109.4712°tetrahedron
6881212π / 290°octahedron
86121218multiple anglescube
12202030302 arctan(2/(1+√5))63.435°icosahedron
n??????

So what's the answer? I don't know, but one thing we have learned is that a cube's points are not all evenly spaced. The angles between them follow a regular pattern. There are twelve edges with an angle between the points of 2 arcsin(1/√3) ≈ 70.528°, and if you include all triangle edges, there are six edges with an angle between the points of 2 arcsin(√2/√3) ≈ 109.4712°.

Continue reading Part 2