Getting rid of triangles, and other ways to Euler

That proof that any convex polyhedron made of pentagons and hexagons must contain at least 12 pentagons rests on Euler’s polyhedron formula: If a convex polyhedron has V vertices, E edges, and F faces, then

V-E+F=2

So how is that proved? Lots of ways, some of which rely on the Jordan curve theorem, so then you need a proof of that. An outline of one that doesn’t use the Jordan curve theorem, Triangle Removal, is as follows.

First, transform the polyhedron into a planar graph. You can think of this as removing one face of the polyhedron, and then stretching the boundaries of that face and deforming the other edges until all the edges lie in a plane. Or you can think of it as putting a light source near one face and a plane on the opposite side: the shadow cast onto the plane is the planar graph. This graph has the same number of vertices and edges as the polyhedron, and apparently one fewer face — until you realize the entire plane exterior to the graph can be thought of as a face too.

Okay, we have our graph. Now do the following: Find any interior face that has more than three edges, and draw a diagonal through it from one vertex to another. Doing that increases the number of edges by 1, and divides one face into two, but leaves the vertices unchanged. That means V-E+F is unchanged. Repeat that until all the interior faces are triangles.

Now do this:

  1. Identify a triangle that has two edges on the border of the graph. If you can’t find one, go to step 2. If you can find one, remove those two edges. This eliminates two edges, one face, and one vertex, so again V-E+F is unchanged. Now repeat step 1.
  2. Identify a triangle that has one edge on the border of the graph. Remove that edge. This eliminates one edge, one face, and no vertices, so again V-E+F is unchanged. Now repeat step 1.

Keep repeating as long as you can. Here I get hand wavy, because I’m less than clear on the argument, but: You don’t want to do step 2 if you can do step 1, because that leads to dead ends — specifically, a graph broken up into two disconnected graphs. Always do step 1 if you can, step 2 only if you can’t do step 1, and the graph will stay connected.

For instance, starting from a (kinda irregular) square pyramid. Here it’s turned into a planar graph with one quadrilateral and three triangular faces (the fourth triangle mapping to the exterior of the graph). The quadrilateral is divided into two triangles, and then triangles are removed one at a time.

Since the graph stays connected, the process continues until there’s only one triangle left. At this point we stop and take a tally: There are 3 vertices, 3 edges, and 2 faces (the interior of the triangle, and the exterior). So V-E+F = 2, and since every step we took preserved the value of V-E+F, this proves V-E+F=2 for the original polyhedron.

Something about that proof appeals to me, even though there’s that one part I’m hazy on.

The Sum of Angles proof I find clearer, but less cute. Here again you turn the polyhedron into a planar graph with straight edges. Now add up the interior angles of all the faces (including the exterior face). For face i, which has k_i edges, the sum of the interior angles is (k_i-2)\pi. Summing over all the faces,

\Sigma_{i=1}^F(k_i-2)\pi = \left(\Sigma_{i=1}^Fk_i-\Sigma_{i=1}^F2\right) = (2E-2F)\pi

But we get the same result if we sum the angles meeting at each vertex. For each interior vertex, the sum is 2\pi, adding up to 2\pi(V-k) where k is the number of vertices on the border. For the vertices on the border, it’s 2(\pi-\theta_i) where \theta_i is the exterior angle at the ith vertex of the exterior polygon, and the 2 is because we include the (equal) contributions of the internal and external polygons. But the sum of the exterior angles of a polygon is 2\pi, so the exterior vertices contribute a total of 2\pi k-4\pi. Altogether, then, the sum is 2\pi V-4\pi.

So (2E-2F)\pi = 2\pi V-4\pi, or E-F = V-2,

Either way, no Jordan curve theorem required! Yay.

Advertisements

Hexagonal filth

I was amused by this report of a petition to change the representation of soccer balls on UK signs. At present the image is of a ball divided into brown and white hexagons. At least on one side.

The problem is, if it’s hexagons all the way around, it’s a geometric impossibility. You can’t have a convex polyhedron consisting solely of hexagons, regular or otherwise. In fact: If a convex polyhedron has only hexagons and/or pentagons as faces, then there must be at least 12 pentagons.

The proof is based on Euler’s polyhedron formula: If a convex polyhedron has V vertices, E edges, and F faces, then

V-E+F=2.

For our hex-and-pent-agon polyhedron, consisting of h hexagons and p pentagons, F = p+h, of course. What’s E? Well, each hexagon has 6 edges and each pentagon has 5, but that counts each edge twice since each edge belongs to two faces. So E = (5p+6h)/2.

Now, at each vertex, at least 3 edges meet. If you add up the number of edges at each vertex over all vertices you get at least 3V; but since each edge contributes 2 to that total, 3V \le 2E.

But from Euler’s formula,

3V = 6+3E-3F \le 2E

or

6-3F \le -E

and substituting our formulas for F and E,

6-3p-3h \le -(5p+6h)/2

or

12-6p-6h \le -5p-6h

or

12-p \le 0

or

p \ge 12.

QED.

(The equality holds if every vertex has 3 edges — or equivalently, 3 faces. In particular, if you’re using only regular hexagons and pentagons, then there isn’t room at a vertex for more than 3 faces to meet there. So for a polyhedron made of regular hexagons and pentagons, or any polyhedron with exactly three hexagons and/or pentagons meeting at each vertex, p = 12.)

Hence the government must be petitioned. As The Aperiodical says, “Ban this hexagonal filth!”

Tangent II

I had a thought about another way to approach that ellipse and circles problem and thought I’d try it on a generalization. Suppose the circle is of arbitrary radius and sitting at an arbitrary point? (You can turn it into a unit radius just by rescaling, but let’s put the radius in explicitly. If nothing else it helps check for errors via dimensional analysis.)

This time instead of working with x and y let’s use the parametric equations

x=a\cos t

y=b\sin t

And now let’s write down the distance D between a point on the ellipse and the center (xc, yc) of the circle:

D(t) = \sqrt{(x-x_c)^2+(y-y_c)^2}=\sqrt{(a\cos t-x_c)^2+(b\sin t-y_c)^2}

The idea here is that if D(t) has a local extremum at t=tt and if D(tt)=r (the radius of the circle) then tt  corresponds to a tangent point. So the plan is to solve dD/dt=0 to get values of tt, and then solve D(tt)=r to get the relation between a and b required for tangency.

Well, easier said than done. The requirement dD/dt=0 leads to

(b^2-a^2)\sin t\cos t-by_c\cos t+ax_c\sin t=0

which I think can be solved in the sense that it can be converted to a cubic in cos t. Ah, no thanks.

So how about a milder generalization? Keep the arbitrary radius and the arbitrary xbut require the circle to sit on the x axis: yc=0. In that case

(b^2-a^2)\sin t\cos t+ax_c\sin t=0

with solutions

\sin t=0 (case [i]) or

\cos t=\frac{ax_c}{a^2-b^2} (case [ii])

(If sin t ≠0 and a2=b2, then the case [ii] formula doesn’t work. But if so, the ellipse is a circle, and dD/dt≠0 unless x= 0: both circles are concentric and every point on the “ellipse” is equidistant from the center of the other circle, and to make that distance be r you have to make the two circles be identical, which isn’t really what I mean by a tangent ellipse. So I’ll only consider a2≠b2.)

For case [i], plug sin t=0 and cos t=±1 into the formula for D and set it equal to r, and the legal (positive) values for a are |xc+r| and |xc–r|. Obviously if a has either of these values then the left or the right end of the ellipse will be tangent to the circle. To find out if it’s exterior or interior requires checking whether the extremum is a minimum or a maximum, for which you need the sign of the second derivative. I haven’t gone there yet. It looks messy.

Case [ii] starts messy and gets messier, until a whole lot of cancellation happens and you’re left with a simple answer. The equation to be solved is

\sqrt{\left(\frac{a^2x_c}{a^2-b^2}-x_c\right)^2+b^2\left(1-\frac{a^2x_c^2}{(a^2-b^2)^2}\right)}=r

which turns into

a^4(b^2-r^2)+a^2(2r^2b^2-2b^4-b^2x_c^2)+(x_c^2b^4+b^6-r^2b^4)=0

and when you solve for ausing the quadratic formula, amazingly everything under the radical sign except b4xccancels and the result is

a^2=b^2\frac{x_c^2\pm x_c^2+2(b^2-r^2)}{2(b^2-r^2)}

The minus sign just gives you a2=b2, which we saw above isn’t allowed for this case so we discard that, and the plus sign gives

a^2=b^2\left(1+\frac{x_c^2}{b^2-r^2}\right)

which, if you set xc=r=1, reproduces the result I got previously. Note that this means if b2–ris negative then |xc| must be less than |b2–r2| to make a2 positive. This just says the y intercept of the circle, which is √(r2xc2), must be greater than b for the ellipse to fit inside the circle. That is, if the ellipse is shorter (vertically) than the circle, then the circle must be close to centered on the origin in order to get two point tangency:

elconstHere r is 5, b is 4, so |xc| must be less than 3 (and it’s about 2.9). Of course in the limit as the ellipse becomes infinitesimally narrow, xc approaches 3 with the tangent point going to (0, 4) and xc, the origin, and the tangent point approaching a right triangle.

Once again, for case [ii] generally, one has to test whether the extremum is a minimum or a maximum to determine if the tangent is interior or exterior. I wonder how horrible that is. I don’t want to find out right now.

 

An elliptical tangent

Another oddball ellipse topic: Let’s suppose you have two unit circles (r=1) adjacent, i.e. tangent, to one another, and you want to draw an ellipse that contains them. But not just any ellipse. The smallest such ellipse.

Establish a coordinate system: The two circles’ centers are at (–1,0) and (1,0); they touch at the origin. One circle extends from the origin to x=2 on the x axis, the other from the origin to x=–2.

This is symmetric under reflection in the x and y axes, so the ellipse will be too: its semimajor and semiminor axes will be on the x and y axes (not necessarily respectively). It’s not “tilted” in other words. And by symmetry, the smallest ellipse containing one of the circles will also contain the other, so we can ignore the circle at (–1,0) and just work with the one at (1,0).

Clearly the ellipse and circle can intersect at 0, 1, 2, 3, or 4 points:

ec

The red unit circle intersects the blue ellipse at four points, the purple ellipse at three, the green ellipse at two, the orange ellipse at one, and the brown ellipse at none. Except when it is at (2, 0) each intersection point occurs as one of a pair at the same x — one at positive y and one at negative y. So there are 0, 1, or 2 distinct x values for the intersection points. In this drawing the orange and brown ellipses are the only two that contain the entire circle.

So what’s the smallest such ellipse containing the entire circle?

Obviously that ellipse must not cross the circle, but must be tangent to the circle from the outside. At least I think that’s obvious! If you imagine you have a video display, with two knobs that control the semimajor axis a and semiminor axis b, then you can think of two ways to achieve tangency. First: Start with a tall, narrow ellipse, one with large b and small a; it intersects the circle at two points with the same x (like the green ellipse above). Now start turning up the a knob. The ellipse gets wider, the intersection points move to the right, and once they’re past x=1 they start getting closer and closer to one another. When a=2 they coalesce to a tangent point at (2, 0) (like the orange ellipse, which intersects only at the tangent point, or the purple one, which has an additional pair of intersections).

The other way is to take a short, wide ellipse — large a (>2) and small b like the blue one. It intersects the circle at two pairs of points, one pair at each of two values of x. Increase and the two pairs approach one another until they coalesce into two tangent points, as in the cyan ellipse below:

ec2

In the first case we have a single solution for x (in real numbers, 0<x≤2) and we drive it toward x=2 by adjusting a to 2. In the second case we have two solutions for x and we drive them together by adjusting b. Now let’s do the math.

The unit circle is given by the equation

(x-1)^2+y^2=1 or y^2=2x-x^2

and the ellipse by

\frac{x^2}{a^2}+\frac{y^2}{b^2}=1 or y^2=b^2(1-\frac{x^2}{a^2})

So the x coordinates of the intersection points are found by solving

2x-x^2=b^2(1-\frac{x^2}{a^2})

for x. This is a quadratic whose solutions are

x=\frac{-a^2\pm a\sqrt{a^2+(b^2-a^2)b^2}}{b^2-a^2}

For the first case we impose a=2:

x=\frac{-4\pm 2\sqrt{4+(b^2-4)b^2}}{b^2-4}

and when you work that out you find one value of x always is 2. But for b > √2, the second value of x is > 2 which is not a valid solution. (In real numbers. That is, x is still real, but y becomes imaginary.) So there is only one intersection, at the tangent point, and the circle is entirely contained in the ellipse. On the other hand, for b < √2, the second value of x is < 2 which means there’s another pair of intersections; this is the purple ellipse above. So the ellipse is tangent to the circle but doesn’t contain the circle.

For the second case (two tangent points) we’re trying to get the two solutions for x to become degenerate; that means

a^2+(b^2-a^2)b^2=0 or a^2=\frac{b^4}{b^2-1} .

The eccentricity has a nice simple relation with b:

\epsilon^2=1-\frac{b^2}{a^2}=1-b^2/\frac{b^4}{b^2-1}=1/b^2

The tangent point x coordinate is given by

x_t=\frac{a^2}{a^2-b^2}=\frac{1}{1-b^2/a^2}=1/\epsilon^2 or x_t=b^2

Now, which ellipses containing the circle have the smallest area and perimeter? We need the ellipse to be tangent to the circle but not to cross it, which means we exclude the high eccentricity a = 2 case (b < √2).

For the low eccentricity a = 2 case of course the smallest area is when b=√2. Then the area is

A=\pi a b=2\sqrt{2}\pi\sim 8.886

For the a > 2 case

A=\pi a b=\pi b\frac{b^2}{\sqrt{b^2-1}}

Finding the minimum by differentiating with respect to b we find

b=\sqrt{3/2}\sim 1.225, a=3\sqrt{2}/2\sim 2.121, A=(3\sqrt{3}/2)\pi\sim 8.162

which is smaller than for the other case, so it’s the winner.

As for the perimeter, even if we use one of Ramanujan’s approximations it’d be a pain to do the algebra to find the minimum, but a little spreadsheet exploration shows it’s at a slightly smaller eccentricity, with b about equal to 1.291.*

Here’s the minimum area ellipse containing both unit circles, to scale:ec3

* Oh, by the way, did you know if you Google “ellipse perimeter” you get an ellipse perimeter calculator using one of Ramanujan’s approximations?

Dividing ellipses

Yeah, I’m still around.

I’ve been thinking about ellipses lately. For Reasons.

Here’s a sort of silly question. Suppose I gave you a circle and asked you to mark four points on it, evenly spaced. You’d probably ask me why I don’t do such a simple thing myself, and hand me back this:

circle4

Now I ask you to do the same for eight points. You say “uh huh” and give me this:

circle8 Then I ask for four points evenly spaced around an ellipse. You sigh exasperatedly and give me this:

ellipse4

And then I ask for eight points on an ellipse.

Now what?

On a circle this is easy. That’s because a circle has continuous rotation symmetry; any rotation by any angle around the center maps the circle into itself. Rotate by 2π/n, 4π/n, 4π/n, … 2nπ/n radians and any point on the circle maps onto n evenly spaced points on the circle. That’s probably not how you thought about it, but that’s a way to do it.

But an ellipse is different. It has only two-fold rotation symmetry: Rotate by π radians and it maps onto itself, but any other angle (in the 0 to 2π range) doesn’t do that.

So is there any sense in which you can mark eight points evenly spaced around an ellipse? (Or seven points, or six, or even three! But let’s talk about eight.)

You know about ellipses. An ellipse centered on the origin whose semimajor axis has length a and lies along the x axis and whose semiminor axis has length b can be described by the parametric equations

x = a\sin t\\y = b\cos t

 where t ranges from 0 to 2π, from which

\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 .

 The elongatedness, or, to use the right term, the eccentricity of an ellipse is

\epsilon=\sqrt{1-(b/a)^2}

An ellipse is the locus of points whose summed distances to two focal points is a constant, and for the above parameterization these two foci lie on the x axis at x_f = \pm a\epsilon. (They’re the magenta points in that last picture up there.)

The parameter t is not the polar angular coordinate θ. The two are related by

\theta = \tan^{-1} ((b/a)\tan t)

That’s the angle between the +x axis and a ray from the origin to the point on the ellipse. Then there’s the focal angle ɸ, between the +x axis and a ray from a focus to the point on the ellipse. Considering the focus at +aε, for points to the right of the focus — x >  — we have

\phi = \tan^{-1}((b \sin t) / (a \cos t - a\epsilon))

while for x <  — we have

\phi = \pi - \tan^{-1}((b \sin t) / (a\epsilon -a \cos t))

The length of an elliptical arc is

 a (E(t_2, \epsilon) - E(t_1, \epsilon))

where E is an elliptic integral. Not easy to calculate, in other words.

An arc and the two line segments connecting the endpoints of the arc to the origin define a central sector whose area is

A(t_1, t_2) = \frac{1}{2}ab(t_2-t_1)

And as a special case of this, the area of an ellipse is A(0,2π) = πab.

What about the area of a focal sector? This is bounded by an arc and the two line segments connecting the endpoints of the arc to a focus. In general, a focal sector can be converted to a central sector by adding one triangle and subtracting another. For instance:

sectors

Focal sector ABF is central sector ABO minus triangle BCO plus triangle ACF. In the case where point A is (a, 0) (at the end of the semimajor axis), triangle ACF disappears and triangle BCO has base  and height b sin t, so the area of that focal sector is the area of the central sector, abt/2, minus the area of the triangle, abε/2 sin t. : (ab/2)(t – ε sin t).

Right.

So back to the question. Eight evenly spaced points on an ellipse. Well, what ways are there to do it on a circle?

I talked about doing on a circle it by mapping a single point via rotations of π/4, π/2, 3π/4, … 2π radians. Equivalently, you can draw rays from the origin at angles of π/4, π/2, 3π/4, … 2π radians from the x axis and mark where the rays cross the circle.

Another way to think about it is: you know the circumference of the circle is 2πr. So divide it up into congruent arcs each of which is 2πr/8 units long.

Yet another way: Think of the circle as a pie and cut it into eight congruent slices.

Approaches like those will work for any number of points. Another, maybe somewhat odd way to think about the eight point case is to mark the points where the tangent lines have slope 0, 1, -1, or undefined.

All of these produce the same result for a circle. What if we try to adapt them for ellipses?

First the angular approach. Divide 2π into eighths… but which 2π? There are really three angles in play here for any point on the ellipse: The parameter angle t, the polar angle θ, and the focal angle ɸ. Well, two focal angles, but they’re symmetric: let’s only consider the +aε focus. For the circle t = θ and there are no foci (or they coincide with the origin and θ = ɸ, if you prefer) but for general ellipses these all differ.

Then the arc approach. You can’t divide the perimeter up into eight congruent arcs, but you can at least make eight arcs of equal length.

Next, the sector approach. Again, you can’t cut your elliptical pie up into congruent slices, but you can at least make your slices the same area. But are you cutting central sector slices or focal sector slices?

Finally the dy/dx approach.

Okay, seven ways to do it: Parameter angles, polar angles, focal angles, arcs, central sectors, focal sectors, and dy/dx. Let’s do this. For each approach compute eight values of t and mark the corresponding points. Ready?

1. Parameter angles. This is easy. t = π/4, π/2, 3π/4, … 2π radians. On an ellipse with eccentricity of 0.8 it looks like this:

ellipse_pangle

I haven’t drawn in any angles because there’s nothing to draw; t doesn’t correspond with any geometrical angles here. On an ellipse with eccentricity 0.99 it looks like this:

ellipse_pangle_99

That’s probably not what you mean by evenly spaced.

2. Polar angles. This is almost as easy. θ = π/4, π/2, 3π/4, … 2π radians and t=\tan^{-1}((a/b)\tan\theta). For the four off-axis points you just get t=\tan^{-1}(\pm a/b). On our 0.8 ellipse, with the polar rays drawn in:

ellipse_poangle

And on our 0.99 ellipse:ellipse_poangle_99Okay, that’s really not what you mean.

3. Focal angles. Just because we can, though it’s not so easy. To get the ɸ = π/4 and ɸ = 3π/4 points you need to solve

\frac{b\sin t}{a\cos t-a\epsilon}=\pm 1

(do that by squaring and substituting 1-\cos^2t for \sin t, giving you a quadratic in \cos t) and for the ɸ = π/2 point it turns out

t=\cos^{-1}\epsilon .

The ɸ = 0 and ɸ = π points I hope are obvious and the others you get by reflection. Result, on the 0.8 ellipse, with the focal rays drawn:

ellipse_fangle

You don’t even want to see the 0.99 ellipse here. Trust me.

4. Arcs. On the whole this seems likely to be the most reasonable way to interpret “evenly spaced”. So how’s it work out? Well, all you have to do is to solve

E(t_{n+1}, \epsilon) - E(t_{n}, \epsilon)=E(2\pi,\epsilon)/8

for t1, t2, and t3 (t0 we’ll set to 0, and the other tn we’ll get from symmetry). Which is… hard. Let’s skip that.

5. Central sectors. Back to easy again; use the central sector area formula. Here it is for 0.8:

ellipse_posect and for 0.99:ellipse_posect_99 Those are equitable slices of elliptical pie. May still not be what you mean by evenly spaced, though.

6. Focal sectors. Uh oh. The area formula has (t – ε sin t) in it; how’re you going to solve that for t? I asked wolframalpha.com and it just laughed at me. Good thing this is guaranteed to be a silly way to interpret “evenly spaced” anyway.

7. dy/dx. Just for grins.The point spacings may not be regular, but their tangent line orientations are! The derivative is

\frac{dy}{dx}=\frac{(b/a)}{\tan t}

so for the off axis points, where the slope is to be +1 or –1, t=\tan^{-1}(\pm b/a). (Compare that to the polar angles method, where we got t=\tan^{-1}(\pm a/b)!) For 0.8:

ellipse_dydxand for comedy relief, 0.99:ellipse_dydx_99

Let’s pretend I never drew that.