More on: What is…Projective Geometry?

This week, I thought I’d go a little deeper into the subject of projective geometry (feel free to reread last week’s post for a refresher).  Why? I think this is a good opportunity to discuss the idea of an algebraic model of a geometry.  Certainly using Cartesian coordinates in the Euclidean plane makes many geometrical problems easier to approach.

So what would a coordinate system in projective geometry look like?  The most commonly used system is homogeneous coordinates.  Let’s see how they work.

The difficulty with adding the line at infinity is that we need infinitely many points in addition to those already in the plane.  Perhaps you might imagine that adding an “infinite” coordinate might do the trick, but there is an alternative — and algebraically simpler — approach.

First, think of the Euclidean plane as being the plane z = 1 in three-dimensional Cartesian coordinates, so that every Euclidean point (xy) is given homogeneous coordinates (xy, 1).  But we don’t want to make the z-coordinate special — we want all the homogeneous coordinates to have similar interpretations.  We accomplish this by giving each point infinitely many names — specifically, for any k ≠ 0, the coordinates (kxkyk) describe the same point as (xy, 1).  Geometrically, you might think of this as saying that the line through  (xy, 1) (except the origin) is, in some sense, the point (xy, 1).

So if z ≠ 0, the point (xyz) in homogeneous coordinates is another name for the Euclidean point (x/zy/z).  But why would you want to do this?

The punch line is that we can now use z = 0 to indicate that a point is on the line at infinity!  We still keep the convention that if k ≠ 0, the homogeneous coordinates (kxky, 0) describe the same point as (xy, 0), as long as x and y are not both 0.

So our system of homogenous coordinates contains all points (xyz) such that not all three coordinates are 0.  Any point with z ≠ 0 corresponds to a Euclidean point, and any point with z = 0 corresponds to a point on the line at infinity.

Is it really worth all this trouble?  There are many interesting features of such a coordinate system — and I’d like to mention a few of them here, omitting the proofs.  There are many resources online that include all the details — one example is the classic Projective Geometry by Veblen and Young available free as an ebook.

Let’s start be looking at equations of lines in projective geometry.  In the Cartesian plane, we may represent a line in the form Ax + By + C = 0, where A, B, and C are not all zero.  In the projective plane, a line has the form form Ax + By + Cz = 0, where A, B, and C are not all zero.  Nice, isn’t it?  This form is also consistent with our system of having many names for a point:  if Ax + By + Cz = 0 and k ≠ 0, then also A(kx) + B(ky) + C(kz) = 0 as well. So no problems there.

But the really neat aspect of this representation is how you can use linear algebra in three dimensions to solve many problems in projective geometry.  This isn’t a post about linear algebra — so I’ll limit myself to just one example.  But in case you do know something about linear algebra, I think you should see how it can be used in projective geometry when homogeneous coordinate are used.

We’ll consider the problem of finding the intersection of two lines, say Ax + By + Cz = 0 and Dx + Ey + Fz = 0.  The form of these expressions should remind you of taking the dot product, so that we can rewrite these expressions as

(A,B,C)\cdot(x,y,z)=(D,E,F)\cdot(x,y,z)=0.

Interpreting these coordinates and coefficients as vectors in three-dimensional space, we observe that the common point (xyz) is simultaneously perpendicular to both (A, B, C) and (D, E, F), since both dot products are zero.  So (xyz) can be found using the cross-product

(x,y,z)=(A,B,C)\times(D,E,F).

Very nice!  Again, there are many such examples, but this is not the place to discuss them….

This algebraic model also suggests another geometric model for the projective plane besides adding a line at infinity to the Euclidean plane.  Begin with the surface of a sphere centered at the origin in three-dimensional Cartesian space, and observe that opposite points on the sphere have homogeneous coordinates that are different names for the same point in the projective plane.

So, in some sense, we have exactly twice as many points as we need — so we identify opposite points on this sphere, so that they are in fact the same point.  (You might recall a similar discussion about points in the post on spherical geometry.)  Thinking about it in another way, we might just consider the top hemisphere of the sphere with only half of the equator, including just one of the endpoints of the semicircle.

And while this model is fairly simple geometrically, it is important to point out that this does not mean that the projective plane lies inside three-dimensional space.  Once we have our hemisphere and semicircle, we have to think about it without any of the surrounding space.  This is not easy to do, but this type of thinking is necessary all the time when studying differential geometry, a topic for another time….

One last benefit to using homogenous coordinates:  it can easily be abstracted to any number of dimensions.  Do you want a projective space?  Just add a plane at infinity to three-dimensional Euclidean space!  Coordinates are easy — all points (x, y, z, w), with not all coordinates equal to 0.  When w ≠ 0, the point (x, y, z, w) corresponds to the Euclidean point (x/w, y/w, z/w), and when w = 0, the point is on the plane at infinity.

And clearly, there would be no need to stop at three dimensions — it is just as easy to create a projective space of four or more dimensions.

Finding a workable system of coordinates for a particular geometry is not always a simple matter — but finding a system that allows problems to be solved easily is often a key step to studying any type of geometry.  I hope this gives you some insight to yet another aspect of the diverse universe of so many different Geometries….

What is…Projective Geometry?

The last type of geometry I discussed was inversive geometry, which is obtained by adding a point at infinity to the Euclidean plane.  Recall that as long as we had a consistent, useful model of this extended plane, it made perfect sense to define this new type of geometry.

Today, we’re going to add a line at infinity — creating what is called a projective geometry.  There are in fact many different types of projective geometries, but let’s just try to understand one at a time….

You might remember one important property of ω, the point at infinity in inversive geometry:  it was on every unbounded curve, and in particular, on every line. We need to be a bit more specific with our projective geometry, in the following sense.  Every line will intersect the line at infinity — denoted by λ — but not every line will intersect at the same point.

Consider all lines with some given slope m.  We then add one point to λ which lies on these lines, but no other lines.  In other words, each point on λ corresponds to an infinite family of parallel Euclidean lines — since now, with the addition of λ, there are no parallel lines in the projective plane.  The point at which two parallel (in the Euclidean sense) lines intersect is determined by their slope.

How does this differ from inversive geometry?  Well, in inversive geometry, if two lines had different slopes, they intersected in two points:  the usual finite point of intersection you learned about in algebra class, as well as ω.  But in projective geometry, two lines with different slopes intersect in only one point, since they intersect the line at infinity in two different points.

What this means is that any two distinct lines always intersect in exactly one point.  See the difference?  Parallel lines (in the Euclidean sense) intersect in a point on λ, and nonparallel (in the Euclidean sense) lines intersect in the same point they did in Euclidean geometry.

Now let’s look at the dual question (recall the discussion of duality, an important concept in spherical geometry):  what about a line between two points?  Two finite points generate a line, as usual.  If one point is finite and one lies on λ, the line generated is that line through the finite point with the slope corresponding to the point on λ.  And if both points are infinite, then the line through them is just λ.

Thus we have the following duality:  two distinct lines determine a unique point, and two distinct points determine a unique line.  Again, duality is an extremely powerful concept in geometry, so the fact that points and lines are dual concepts really is a legitimate justification for thinking about projective geometry.

Projective plane geometry is a broad subject — but some of my favorite objects to look at in projective geometry are the conic sections:  ellipses, parabolas, and hyperbolas.  This is because from the point of view of projective geometry, they are, in a sense which we’ll look at right now, all the same.

This sounds odd at first reading, but follow along.  The first question we need to consider is what points on λ lie on unbounded curves.  For lines, it’s easy — it’s just the point on λ corresponding to the slope of the line.

Now what about a parabola?parabola

You can see from the image that as points on the parabola move further away from its vertex, the tangents have slopes of ever-increasing magnitude.  Determining the precise slopes is an easy exercise in calculus — but what is important is that the tangent lines approach, in slope, the axis of the parabola.  In this case the axis is vertical, but of course the parabola may be rotated.

What this means is that the parabola intersects the line at infinity in the point corresponding to the slope of its axis.  Again, the tangent lines on either side approach this slope, but from two directions — from above and from below.

Now hold this thought while we look at a hyperbola.

hyperbola

Let’s see how we travel along the hyperbola.  As we move to the upper right toward the open red circle, we are moving closer to the red dashed asymptote — meaning we approach the point on λ corresponding to the slope of the red asymptote.  But here is where it becomes interesting:  as we cross the line at infinity, we come back along the asymptote toward the filled red circle on the other branch of the hyperbola!

Then we continue moving along the left branch, getting continually closer to the blue asymptote, approaching that point on λ corresponding to the slope of the blue asymptote as we pass through the blue filled circle.  Then we cross the line at infinity again, and jump to the right branch of the hyperbola toward the open blue circle.

Can you see what this means?  In projective geometry, a hyperbola does not have two separate branches.  Adding the line at infinity allows us a means to jump between the two branches.

Let’s look at these scenarios from a slightly different perspective.  Suppose that somehow, we can actually draw the line at infinity.  It’s the blue dashed line in the figure below.  Easy.

conics

Can you see where we’re going with this?  The left circle represents an ellipse, since it is a bounded curve and cannot intersect λ.  The middle circle represents a parabola — it’s a curve which intersects the line at infinity at exactly one point, and so is actually tangent to λ.  The right circle represents a hyperbola, since it intersects the line at infinity at two points.  It may look strange from this perspective, but this right circle really does represent the hyperbola illustrated above.

To summarize:  if a conic does not intersect the line at infinity, we call it a Euclidean ellipse, if it is tangent to λ, we call it a Euclidean parabola, and if it intersects λ in two points, we call it a Euclidean hyperbola.

Because you see, in projective geometry, there is no distinguished line.  Every line is just like any other.  So, in some sense, these is just one conic section in projective geometry!

What we have looked at today is what would be called an embedding of the Euclidean plane in the projective plane.  We saw how we could just add a line at infinity with certain properties, and our plane would behave “projectively.”  But from the perspective of projective geometry, you’ve just got conic sections and lines, with possibly 0, 1, or 2 intersection points as illustrated above.  A little mind-blowing, but absolutely true.

Of course we’ve only been able to scratch the surface of this really amazing geometrical world today.  Hopefully you will be inspired to learn a little bit more about it….

More on: What is…Inversive Geometry?

The more I thought about it, the more I realized I just couldn’t stop at just one post on inversive geometry.  There is so much interesting geometry to discuss….

Cardioid

This image of a cardioid, made up of a collection of tangent circles, is one of my favorite geometrical constructions.  It’s created by beginning with a base circle (in black).  Choose any point on the circle (like the one in black), which we take to be the origin.

Cardioid2.png

Now for any other point on the black circle (like the point in red), draw a circle with that point as center, and the radius as the distance from the origin, as in the figure.  If you do this several times, the circles you draw will envelope a cardioid.

Why do you get a cardioid?  It’s actually not too difficult to prove using inversive geometry.  We won’t go through all the details, but you’ll see enough to get the gist of the proof.

So let’s go!  There’s actually a lot going on once you’ve added the point at infinity, ω.  If you’ve forgotten about ω, you might want to look at Day091 to refresh your memory.  One property of ω which will be important to our discussion today is that ω lies on any curve which is unbounded.  And the simplest unbounded curve is just a line.

So imagine a line, and some point P on that line.  Now chose a direction long the line, and think about moving along the line in that direction.  What happens?

Well, eventually, you’ll start moving further and further away from the origin.  And as you keep moving further from the origin, you’re actually moving “closer” to the point at infinity.  Not closer in a numerical sense of the distance from ω, since you are always infinitely far away from ω.  But closer in the sense that the line “ends” at the point at infinity.  If ω lies on the line, you’ll need to able to get there — even it takes forever….

Yeah, a bit to wrap your head around.  But it gets even better!  Think back to where you started — the point P — and then move along the other direction along the line.  Keep going…as you approach the point at infinity from the other side of the line.

Do you see what’s happening?  Both ends of the line actually meet at ω!  Yes, the line is a closed curve in inversive geometry, like a circle is in Euclidean geometry.

We’ll come back to this point in a moment, but next we want to ask the following question:  what is the inverse curve of a line?  Recall that the inverse curve of a line is that curve obtained by taking all the individual points on a line, and then taking all of their inverse points.

Interestingly, the inverse curve turns out to be a circle — and not just any circle, but a circle which goes through the origin.  As the proof isn’t all that difficult, we’ll take a few moments to work through it.

figuresinv2

So suppose the red circle centered at O has radius 1, and choose a point P.  Now draw the line through P such that the segment OP is perpendicular to the line, and consider another point Q on this line.  Thus, triangle OPQ has a right angle at P.

Since the point at infinity, ω, is on the line, its inverse point, ω′ = O, must lie on the inverse curve.  Thus, the inverse curve (shown in blue) must pass through the origin. Of course P and Q′, the inverse points of P and Q, must also lie on the inverse curve.

Then by the property of inverse points, [OP]\cdot[OP']=[OQ]\cdot[OQ']=1, and so

\dfrac{[OP]}{[OQ]}=\dfrac{[OQ']}{[OP']}.

But because inverse points lie on the same ray through the origin, then \angle POQ and \angle Q'OP' must have the same measure, making triangles \Delta POQ and \Delta Q'OP' similar triangles.

What does this mean?  This implies that \angle OQ'P' is also a right angle.  To summarize:  given any point Q on the line, its inverse point Q′  has the property that when joined to O and P′, a right triangle is formed with a right angle at Q′.

But because any triangle inscribed in a semicircle is a right triangle, this means that the set of all inverse points Q forms a circle with diameter OP′.  Neat!

Thinking back to ω being on the line, we see that as we begin at P and move either direction along the line toward the point at infinity, here’s what we’re doing on the inverse curve:  we’re starting at the point P′ and moving either direction around the circle toward the origin.  It really does make sound geometrical sense.

Will this work for any line?  If you think about it for a moment, you’ll find that it does…almost.  Our geometrical argument fails if the line actually goes through the origin.  But it shouldn’t be difficult to convince yourself that the inverse curve of a line going through the origin is actually the same line!  The two points where the line intersects the circle of inversion stay in the same place, but the other points switch in pairs.

Where are we going with all this?  It turns out that adding the point at infinity does, in some sense, make lines behave like circles — we can even imagine a line as a “circle with infinite radius.” And where is the center of this circle of infinite radius?  The point at infinity, of course….

As mentioned last week, the inverse curves of circles not passing through the origin are also circles not passing through the origin.  To summarize:

  • Inverses of circles not passing through the origin are also circles not passing through the origin;
  • Inverses of circles passing through the origin are lines not going through the origin (and vice versa);
  • Inverses of lines through the origin are also lines through the origin, and each such line is its own inverse.

Now here’s the next step.  Given the close relationship between lines and circles in inversive geometry, we define a Circle in inversive geometry (capital “C”, like we did in spherical geometry) to be either a line or circle.  Then here’s the revised summary:

  • Inverses of Circles are Circles.

Beautifully simple.  The ability to make simple statements like this with real geometrical meaning is one more reason why inversive geometry it so very interesting.

And with that, we’ll have to call it a week….  In the next (and final) post on inversive geometry, we’ll briefly look at the algebra of inverse curves, and finish the cardioid construction mentioned above.  Until then!

 

What is…Inversive Geometry?

It’s been a while since we’ve looked at a new type of geometry, so today I’d like to introduce inversive geometry.  Let’s look at a few pictures first for some motivation.

Day091a

We would like to consider the operation of inverting points, as illustrated above.  Suppose the red circle is a unit circle, the white dot is the origin, and consider the blue point P.  Now define P′ (the orange dot) to be the inverse point of P as follows:  draw a ray from the origin through P, and let P′ be that point on the ray such that

[OP]\cdot[OP']=1,

where [AB] denotes the distance from A to B. That is, when you multiply the distances from the origin of a point and its inverse point, you get 1.

Now why would you want to do this?  It turns out this operation is actually very interesting, and has many unexpected consequences.  Consider the circles in the figure below.

Day091b

Start with the blue circle.  Now for every point P on the blue circle, find its inverse point P′, and plot it in orange.  The result is actually another circle!  Yes, it works out exactly, although we won’t prove that here.  Note that since every point on the blue circle is outside the unit circle (that is, greater than a distance of 1 from the origin), every inverse point on the orange circle must be inside the unit circle (that is, less than a distance of 1 from the origin).

This is just one geometrical property of inversion, and there are many others.  I just want to suggest that the operation of inversion has many interesting properties.

If you pause a moment to think about this operation, you’ll notice there’s a little snag.  Not every point has an inverse point.  There’s just one point which is problematic here:  the origin.  According to the definition,

[OO]\cdot[OO']=1.

But the distance from the origin to itself is just 0, and it is not possible to multiply 0 by another number and get 1, since 0 times any real number is still 0.

Unless…could we somehow make the distance from O to O′ infinite?  It should be clear that O′ cannot be a point in the plane different from the origin, since any point in the plane has a finite distance to the origin (just use the Pythagorean theorem).

So how do we solve this problem?  We add another point to the usual Euclidean plane, called the point at infinity, which is usually denoted by the Greek letter ω.

You might be thinking, “Hey, wait a minute!  You can’t just add a point because you need one.  Where would you put it?  The plane already extends out to infinity as it is!”

In a sense, that’s correct.  But remember the idea of this thread — we’re exploring what geometry is.  When we looked at taxicab geometry, we just changed the distance, not the points.  And with spherical geometry, we looked at a very familiar geometrical object:  the surface of a sphere.  We can also change the points in our geometrical space.

How can we do this?  Though perhaps a simplification, we must do this consistently as long as it is interesting.

What does this mean?  In some sense, I can mathematically define lots of things.  Let’s suppose I want to define a new operation on numbers, like this:

a\otimes b=a^2+37b.

Wow, we’ve just created something likely no one has thought of before!  And yes, we probably have — and for good reason.  This operation is not very interesting at all — no nice properties like commutativity or associativity, no applications that I can think of (what are you going to do with the 37?).  But it is a perfectly legitimate arithmetical operation, defined for all real numbers a and b.

As I tried to suggest earlier, the operation of inversion is actually quite interesting.  So it would be very nice to have a definition which allowed every point to have an inverse point.

But if we want to add ω, we must do so consistently.  That is, the properties of ω cannot result in any contradictory statements or results.

It turns out that this is in fact possible — thought we do have to be careful.  Although we can’t go into all the details of adding the point at infinity to the plane, here are some important properties that ω has:

  1. The distance from ω to any other point in the plane is infinite;
  2. ω lies on any unbounded curve (like a line or a parabola, but not a circle, for example);
  3. The inverse point of ω is the origin; that is, O′ = ω and ω′ = O.

So we can create an entirely consistent system of geometry which contains all the points in the Euclidean plane plus a point at infinity which is infinitely far away from every other point.  We usually call the Euclidean plane with ω added the extended plane.

With the new point, we can now say that every point in the extended plane has a unique inverse point.

This idea of adding a point at infinity is also important is other areas of mathematics.  In considering the complex plane — that is, the set of points of the form abi, where i is a solution of the equation x^2+1=0 — it is often useful to add the number ∞, so that division by 0 is now possible.  This results in the extended complex plane, and is very important in the study of complex analysis.

The point at infinity is also important in defining stereographic projection.  Here, a sphere is placed on the plane, so that the South pole is the origin of the plane.  The sphere is then projected onto the plane as follows:  for any point on the sphere, draw a ray from the North pole through that point, and see where it intersects the plane.

 

Stereographic_projection_in_3D
Courtesy the Wikipedia Commons.

Where does the North pole get mapped to under this projection?  Take one guess:  the point at infinity!

So here is another new geometry!  As we get introduced to more and more various geometrical systems, I hope you will continue to deepen your intuition about the question, What is a geometry?

Imagifractalous! 5: Fractal Binary Trees III

Last week I talked about working with binary trees whose branching ratio is 1 or greater.  The difficulty with having a branching ratio larger than one is that the tree keeps growing, getting larger and larger with each iteration.

But when you work with software like Mathematica, for example, and you create such a tree, you can specify the size of the displayed image in screen size.

So the trees above both have branching ratio 2 and branching angle of 70°.  The left image is drawn to a depth of 7, and the right image is drawn to a depth of 12.  I specified that both images be drawn the same size in Mathematica.

But even though they are visually the same size, if you start with a trunk 1 unit in length, the left image is about 200 units wide, while the second is 6000 units wide!

So this prompted us to look at scaling back trees with large branching ratios.  In other words, as trees kept getting larger, scale them back even more.  You saw why this was important last week:  if the scale isn’t right, when you overlap trees with r less than one on top of the reciprocal tree with branching ratio 1/r, the leaves of the trees won’t overlap.  The scale has to be just right.

2017-04-08ris2d.png

So what should these scale factors be?  This is such an interesting story about collaboration and creativity — and how new ideas are generated — that I want to share it with you.

For your usual binary tree with branching ratio less than one, you don’t have to scale at all.  The tree remains bounded, which is easy to prove using convergent geometric series.
2017-01-20ris1

What about the case when r is exactly 1, as shown in the above figure?  At depth n, if you start with a trunk of length 1, the path from the base of the trunk to the leaf is a path of exactly n + 1 segments of length 1, and so can’t be any longer than n + 1 in length.  As the branching angle gets closer to 0°, you do approach this bound of n + 1.  So we thought that scaling back by a factor of n + 1 would keep the tree bounded in the case when r is 1.

What about the case when r > 1?  Let’s consider the case when r = 2 as an example.  The segments in any path are of length 1, 2, 4, 8, 16, etc., getting longer each time by a power of 2.  Going to a depth of n, the total length is proportional to 2^n in this case.  In general, the total length is about 2\cdot r^n for arbitrary r, so scaling back by a factor of r^n would keep the trees bounded as well.

So we knew how to keep the trees bounded, and started including these scaling factors when drawing our images.  But there were two issues.  First, we still had to do some fudging when drawing trees together with their reciprocal trees.  We could still create very appealing images, but we couldn’t use the scale factor on its own.

And second — and perhaps more importantly — Nick had been doing extensive exploration on his computer generating binary trees.  Right now, we had three different cases for scaling factors, depending on whether r < 1, r = 1, or r > 1.  But in Nick’s experience, when he moved continuously through values of r less than 1 to values of r greater than one, the transition looked very smooth to him.  There didn’t seem to be any “jump” when passing through r = 1, as happened with the scale factors we had at the moment.

I wasn’t too bothered by it, though.  There are lots of instances in mathematics where 1 is some sort of boundary point.  Take geometric series, for example.  Or perhaps there is another boundary point which separates three fundamentally different types of solutions.  For example, consider the quadratic equation

x^2+c=0.

The three fundamentally different solution sets correspond to  c < 0, c = 0, and c > 0.  There is a common example from differential equations, too, though I won’t go into that here.  Suffice it to say, this type of trichotomy occurs rather frequently.

I tried explaining this to Nick, but he just wouldn’t budge.  He had looked at so many binary trees, his intuition led him to firmly believe there just had to be a way to unify these scale factors.

I can still remember the afternoon — the moment — when I saw it.  It was truly beautiful, and I’ll share it in just a moment.  But my point is this:  I was so used to seeing trichotomies in mathematics, I was just willing to live with these three scale factors.  But Nick wasn’t.  He was tenacious, and just insisted that there was further digging to do.

Don’t ask me to explain how I came up with it.  It was like that feeling when you just were holding on to some small thing, and now you couldn’t find it.  But you never left the room, so it just had to be there.  So you just kept looking, not giving up until you found it.

And there is was:  if the branching ratio was and you were iterating to a depth of n, you scaled back by a factor of

\displaystyle\sum_{k=0}^n r^k.

This took care of all three cases at once!  When r < 1, this sum is bounded (think geometric series), so the boundedness of the tree isn’t affected.  When r = 1, you just get n + 1 — the same scaling factor we looked at before!  And when r > 1, this sum is large enough to scale back your tree so it’s bounded.

Not only that, this scale factor made proving the Dual Tree Theorem so nice.  The scaling factors for a tree with r < 1 and its reciprocal tree with branching ratio 1/r matched perfectly.  No need to fudge!

This isn’t the place to go into all the mathematics, but I’d be happy to share a copy of our paper if you’re interested.  We go into a lot more detail than I ever could in a blog post.

This is how mathematics happens, incidentally.  It isn’t just a matter of finding a right answer, or just solving an equation.  It’s a give-and-take, an exploration, a discovery here and there, tenacity, persistence.  A living, breathing endeavor.

But the saga isn’t over yet….  There is a lot more to say about binary trees.  I’ll do just that in my next installment of Imagifractalous!

Imagifractalous! 4: Fractal Binary Trees II

Now that the paper Nick and I wrote on binary trees was accepted for Bridges 2017 (yay!), I’d like to say a little more about what we discovered.  I’ll presume you’ve already read the first Imagifractalous! post on binary trees (see Day077 for a refresher if you need it).

Recall that in that post, I discussed creating binary trees with branching ratios which were 1 or larger.  Below are three examples of binary trees, with branching ratios less that 1, equal to 1, and larger than 1, respectively.

2016-12-18threetrees.png

It was Nick’s insight to consider the following question:  how are trees with branching ratio r related to those with branching ratio 1/r?  He had done a lot of exploring with graphics in Python, and observed that there was definitely some relationship.

Let’s look at an example.  The red tree is a binary tree with branching ratio r less than one, and the gray tree has a branching ratio which is the reciprocal r.  Both are drawn to the same depth.

2016-12-03-doubletree1.png

Of course you notice what’s happening — the leaves of the trees are overlapping!  This was happening so frequently, it just couldn’t be coincidence.  Here is another example.

tree1

Notice how three copies of the trees with branching ratio less than one are covering some of the leaves of a tree with the reciprocal ratio.

Now if you’ve ever created your own binary trees, you’ll likely have noticed that I left out a particularly important piece of information:  the size of the trunks of the trees.  You can imagine that if the sizes of the trunks of the r trees and the 1/r trees were not precisely related, you wouldn’t have the nice overlap.

Here is a figure taken from our paper which explains just how to find the correct relationship between the trunk sizes.  It illustrates the main idea which we used to rigorously prove just about everything we observed about these reciprocal trees.

tree2

Let’s take a look at what’s happening.  The thick, black tree has a branching ratio of 5/8, and a branching angle of 25°.  The thick, black path going from O to P is created by following the sequence of instructions RRRLL (and so the tree is rendered to a depth of 5).

Now make a symmetric path (thick, gray, dashed) starting at P and going to O.  If we start at P with the same trunk length we started with at O, and follow the exact same instructions, we have to end up back at O.

The trick is to now look at this gray path backwards, starting from O.  The branches now get larger each time, by a factor of 8/5 (since they were getting smaller by a factor of 5/8 when going in the opposite direction).  The size of the trunk, you can readily see, is the length of the last branch drawn in following the black path from O to P.  This must be (5/8)5 times the length of the trunk, since the tree is of depth 5.

The sequence of instructions needed to follow this gray path is RRLLL.  It turns out this is easy to predict from the geometry.  Recall that beginning at P, we followed the instructions RRRLL along the gray path to get to O.  When we reverse this path and go from O to P, we follow the instructions in reverse — except that in going in the reverse direction, what was previously a left turn becomes a right turn, and vice versa.

So all we need to do to get the reverse instructions is to reverse the string RRRLL to get LLRRR, and then change the L‘s to R‘s and the R‘s to L‘s, yielding RRLLL.

There’s one important detail to address:  the fact that the black tree with branching ratio 5/8 is rotated by 25° to make everything work out.  Again, this is easy to see from the geometry of the figure.  Look at the thick gray path for a moment.  Since following the instructions RRLLL means that in total, you make one more left turn than you do right turns, the last branch of the path must be oriented 25° to the left of your starting orientation (which was vertical).  This tells you precisely how much you need to rotate the black tree to make the two paths have the same starting and ending points.

Of course one example does not make a proof — but in fact all the important ideas are contained in this one illustration.  It is not difficult to make the argument more general, and we have successfully accomplished that (though this blog is not the place for it!).

If you look carefully at the diagram, you’ll count that there are exactly 10 leaves in common with these two trees with reciprocal branching ratios.  There is some nice combinatorics going on here, which is again easy to explain from the geometry.

You can see that these common leaves (illustrated with small, black dots) are at the ends of gray branches which are oriented 25° from the vertical.  Recall that this specific angle came from the fact that there was one more L than there were R‘s in the string RRLLL.

Now if you have a sequence of 5 instructions, the only way to have exactly one more L than R‘s is to have precisely three L‘s (and hence two R‘s).  And the number of ways to have three L‘s in a string of length 5 is just

\displaystyle{5\choose3}=10.

Again, these observations are easy to generalize and prove rigorously.

And where does this take us?

canopies.png

On the right are 12 copies of a tree with a braching ratio of r less than one and a branching angle of 30°, and on the left are 12 copies of a tree with a reciprocal branching ratio of 1/r, also with a branching angle of 30°.  All are drawn to depth 4, and the trunks are appropriately scaled as previously discussed.

These sets of trees produce exactly the same leaves!  We called this the Dual Tree Theorem, which was the culmination of all these observations.  Here is an illustration with both sets of trees on top of each other.

2016-12-14gtree.png

As intriguing as this discovery was, it was only the beginning of a much broader and deeper exploration into the fractal world of binary trees.  I’ll continue a discussion of our adventures in the next installment of Imagifractalous!

What is…Spherical Geometry?

This week, we’ll look at another type of geometry, namely spherical geometry.  Quite simply, this is the geometry of a sphere.  Here, a sphere is a set of points equidistant from a given center.  In other words, throughout this post, you should imagine only a surface, with nothing inside it — think of the rind of an orange, without any of the slices.  I began to describe spherical geometry in my original post, What is a Geometry?, so I’ll briefly summarize the ideas in that post first.  It wouldn’t hurt to review it…

From a Euclidean standpoint, there are points on the sphere, but obviously no straight lines.  In spherical geometry, we define a Point to be a pair of antipodal points on the sphere, and a Line to be a great circle on the sphere.  This results in two nice theorems of spherical geometry:  any two distinct Lines determine (intersect in) a single Point, and any two distinct points determine a single Line.

This is a departure from Euclidean geometry, for this means that there are no parallel Lines in spherical geometry, since distinct Lines always intersect.  But there is something more going on here.

Consider the statement “Any two distinct Lines determine a single Point.”  Now perform the following simple replacement:  change the occurrence of “Line” to “Point,” and vice versa.  This gives the statement “Any two distinct Points determine a single Line,”  and is called the dual of the original statement.

Thus, we have the situation that some statement and its dual are both true.  Now if this is true of some set of statements in spherical geometry — that the dual of each statement is true — and we derive a new result from this set of statements, then the following remarkable thing happens.  Since the dual of any statement we used is true, then the dual of the new result must also be true!  Just replace each statement used to derive the new result with its dual, and you get the dual of the new result as a true statement as well.

This is the principle of duality in mathematics, and is a very important concept.  We will encounter it again when we investigate projective geometry.

Triangles and trigonometry are different on the sphere, as well.  A spherical triangle is composed of three arcs of great circles, as in the image below.

Fig31.png

If this were Earth, you could imagine starting at the North Pole, following 0 degrees of longitude to the Equator (shown in yellow), follow the Equator to 30 degrees east longitude, then follow this line of longitude back to the North Pole.

On the sphere, though, sides of a triangle are actually angles.  Sure, you could measure the length of the arcs given the radius of the sphere, but that’s not as useful.  Consider the choice of units on the Earth — kilometers or miles?  We don’t want important  geometrical results to depend on the choice of units.  So a side is specified by the angle subtended by the arc at the center of the sphere.  This makes sense since the sides are arcs of great circles, and the center of any great circle is the center of the sphere.

The angles between the sides are angles, too!  A great circle is just the intersection of a plane passing through the origin and the sphere.  So the angle between any two sides is defined to be the angle between the planes which contain them.

Really nothing from Euclidean trigonometry is valid on the sphere.  For example, if you look at the triangle above, you can see that the angles between the sides are 30, 90, and 90 degrees.  These angles add to 210!  In fact, the three angles of a triangle always add up to more than 180 degrees on a sphere.  (You may notice that the sides of this triangle are also 30, 90, and 90 degrees, but this is just a coincidence.  The sides and angles are usually different.)

If A, B, and C are the angles of a spherical triangle, it turns out that the area of the triangle is proportional to ABC – 180.  This means that the smaller a triangle is, the closer the angle sum is to 180 degrees.

sphtriangle

There is no Pythagorean Theorem on the sphere, either.  In addition, if a, b, and c are the sides opposite angles A, B, and C, respectively, then we have formulas like

\cos c=\cos a\cos b+\sin a\sin b\cos C

and

\cos C=-\cos A\cos B+\sin A\sin B\cos c.

One interesting consequence of the second of these formulas is this.  If you know the angles of a triangle, you can determine the sides.  You can’t do this in Euclidean trigonometry, since the triangles may be similar, but of different sizes.  In other words, there are no similar triangles on the sphere.  Spherical triangles are just congruent, or not. You can’t have two different triangles with the same angles.

For now, we’ve considered our sphere as being embedded in a Euclidean space.  The definition of this surface is easy:  just choose a point as the center of your sphere, and then find all points which are a given, fixed distance — the radius of the sphere — from that point.  Sounds easy enough.

But can you imagine a sphere without thinking of the three-dimensional space around it?  Or put another way, imagine you were a tiny ant, on a sphere of radius 1,000,000 km.  That’s over 150 times the radius of the Earth!  How would you know you were actually on the surface of a sphere?  If you were that small and the sphere were that large, it would seem awfully flat to you….

So how could you determine the sphere was curved?  This is a question for differential geometry, which among other things, is about the geometry of a surface without any reference to a space it’s embedded in.  This is called the surface’s intrinsic geometry.

As an example of looking at the intrinsic geometry of the sphere, consider Lines.  Now you can’t say they’re great circles any more, since this relies on thinking of a sphere as being embedded in three-dimensional space; in other words, its extrinsic geometry.  You need the concept of a geodesic — in other words, the idea of a “shortest path.”

So if you’re the ant crawling between two points on a sphere, and you wanted to take the shortest path, you would have to follow a great circle arc.  So it is possible to define Lines only using properties of the surface itself.  But the mathematics to do this is really extremely challenging.

Lots of new ideas here — but we’ve just scratched the surface of a study of spherical geometry.  You can see how very different spherical geometry is from both Euclidean and taxicab geometry.  Hopefully you’re well on your way to wrapping your head around our original question, What is a Geometry?….