## 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.

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.

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.

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: 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.

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.

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.

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.

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.

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.

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?

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.

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.

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.

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?….

## A New Cantor Set?

Although we’ll do a little review, this post assumes some familiarity with the Cantor set as well as working with fractions in bases other than 10.

So what is the Cantor set?

The usual geometrical definition is to begin with a line segment of length one (as shown at the top of the figure).  Next, remove the middle third of that segment, so that two segments of length 1/3 are formed.  Then remove the middle thirds from those segments, and continue recursively.

Even though — after this process is repeated infinitely, of course — you remove segments whose lengths sum to 1, there are still infinitely many points left!  (Actually, uncountably infinitely many, although this observation is not necessary for our discussion.)

There are many ways to describe the remaining points, but one common way is to say that the Cantor set consists of all those numbers between 0 and 1 (inclusive) which, when written in base 3, may be written only with 0’s and 2’s.

Again, we’ll briefly review.  We have .23 = 2/310, for example — since the places after the ternary point (no “deci”mals here) represent powers of 1/3.

So if we wanted to find 3/4 in base 3, we note that we’d need 2/3 = 0.23, but there would be 1/12 left over. This is smaller than 1/9, so we’re at 0.203 so far. Next, we need 2/27, giving 0.2023, with 1/108 left over. And so on. The result is that 3/4 is equal to 0.202020…3, where the “20” repeats. This can also be shown using infinite geometric series, if desired:

$\dfrac34=\dfrac{2/3}{1-1/9}.$

Surprisingly, the idea for a possibly new type of “Cantor set” came from studying binary trees!  I say possibly new, since I couldn’t find any reference to such a set online, but of course that doesn’t mean someone else hasn’t come across it.  And I call it a type of Cantor set since it may also be formed by taking out thirds of segments, but in a slightly different way than described above.

Now I’ve talked a bit about binary trees before, so I won’t go into great detail.  But here is the important idea:  when you make a branch, you’re pointing in some particular direction, and then turn either left or right, but you can’t just keep going in the same direction.

So what if you looked at ternary expansions, and as you added digits, you had the option of adding 1 to the previous digit (like turning left), or subtracting 1 (like turning right), but you couldn’t use the same digit twice consecutively.  So 0.21021201 would be OK (we’ll drop the 3 subscripts since we’ll be working exclusively in base 3 from now on), but 0.12002120 would not be allowed since there are consecutive 0’s.

Note that adding 1 to 2 gives 0 in base 3, and subtracting 1 from 0 gives 2.  So essentially, starting with 0., you build ternary expansions with the property that each digit is different from the previous one.  And, of course, the expansions must be infinite….

What do iterations of this scheme look like?

We start with a segment of length 1.  Recall we begin with 0., so that means the ternary expansions may begin with 0.1 or 0.2.  Expansions beginning with 0.0 are not allowed, so this precludes the first third of the segment.

Now here comes the interesting part!  On the second iteration, (the third line from the top), we remove different thirds from the first two segments.  Since the 0.1 may continued onto 0.10 or 0.12, but not 0.11, we remove the middle third from the 0.1 segment.  Further, 0.2 may be continued as 0.20 or 0.21, but not 0.22, so we remove the last third of the 0.2 segment.  The iteration process is not symmetrical.

We continue on….  Since 0.10 may be continued as 0.101 or 0.102, but not 0.100, we remove the first third of the 0.10 segment.  You get the idea.  Seven iterations of this procedure are shown in the figure above.

Note that since the process for creating the original Cantor set is symmetrical, this imposes a self-similarity on the set itself.  The Cantor set is exactly the union of two duplicate copies of the original, scaled by a factor of 1/3.

In other words, the Cantor set may also be created using an iterated function system with the following two transformations:

$y=\dfrac13x,\qquad y=\dfrac13x+\dfrac23.$

What about the self-similarity of the new Cantor set?  To help in seeing this, here’s a slightly more detailed version of the iteration scheme.

Is there any self-similarity here?  Yes, but the fewest number of transformations I’ve found to describe this self-similarity is five.  The curious reader is welcome to find fewer!

It isn’t hard to see the five vertical bands in this figure — the first three look the same (although the second one appears to be reflected), and the last two also look the same, although reflections of each other.

The first band is all ternary expansions in this new set beginning with 0.10.  How do these relate to the whole set?  Well, 1/9 of the set consists of expansions beginning with 0.001… or 0.002…, and then adding digits different from those previous.  Adding 1/3 therefore gives all expansions beginning with 0.101… or 0.102…, and then adding different digits.  This implies that the self-similarity describing the first vertical band is

$y=\dfrac 19x+\dfrac13.$

The second band consists of those expansions in our strings beginning with 0.12.  But if x is an expansion in our set beginning with 0.10, then 1 – x must be an expansion in our set beginning with 0.12, since we may write 1 as .22222…, repeating.  Therefore, the second band is represented by the transformation

$y=1-\left(\dfrac 19x+\dfrac13\right)=\dfrac23-\dfrac19x.$

We can think of the third band just as we did the first — except that this band consists of number beginning with 0.20 (rather than 0.10).  So this band is represented by the transformation

$y=\dfrac 19x+\dfrac23.$

The last two bands consist of those expansions beginning with 0.21.  Here, we break into the two cases 0.210 and 0.212, and use our previous work.  For example, those beginning with 0.210 can be found by taking those beginning with 0.10, dividing by 3 to get expansions beginning with 0.010, and then adding 2/3 to get expansions beginning with 0.210:

$y=\dfrac13\left(\dfrac 19x+\dfrac13\right)+\dfrac23=\dfrac1{27}x+\dfrac79.$

We describe the self-similarity of the last band — those expansions beginning with 0.212 — analogously:

$y=\dfrac13\left(\dfrac23-\dfrac 19x\right)+\dfrac23=\dfrac89-\dfrac1{27}x.$

These are five transformations which describe the self-similarity of the new Cantor set.  I haven’t rigorously proved yet that you can’t do it in fewer, but I think this is the case.

Of course this is just the beginning — you can use the same rule in any base.  That is, begin with 0., and either add or subtract one from the previous digit.  In base 4, you get nice self-similarity, but it gets more involved in higher bases.  In bases higher than 3, you can also use the rule that the next digit in the expansion is different than the previous — and this gives yet another class of Cantor sets.  I’ll leave you to investigate, and perhaps I’ll write again about these Cantor sets when I find out more!

## What is…Taxicab Geometry?

It’s time to start exploring different geometries!  Today we’ll look at taxicab geometry because algebraically, it’s the easiest one to work with.  I discussed it briefly before — recall that lines and points are the same as those in the Euclidean geometry we’re used to, but the idea of distance is different.  Here, the distance between two points P and Q is how far a taxi would have to drive on a rectangular grid to get from P to Q.

You can see from the figure that the distance between (-2,3) and (3,-1) is 9, since you’d have to drive nine blocks to get from one point to the other.  This might seem simple enough, but the situation is quite a bit different from Euclidean geometry.

In Euclidean geometry, the shortest distance between two points is a straight line segment.  If you deviate from this segment in any way in getting from one point to the other, your path will get longer.

In taxicab geometry, there is usually no shortest path.  If you look at the figure below, you can see two other paths from (-2,3) to (3,-1) which have a length of 9.

Strange!  There are a few exceptions to this rule, however — when the segment between the points is parallel to one of the axes.  For example, the distance from (0,0) to (4,0) is just 4 — and there’s only one way to get there along a path of length 4.  You’ve got to travel along the line segment joining (0,0) and (4,0).

Well, perhaps “strange” is the wrong word.  All of this is perfectly normal in taxicab geometry….

Now let’s take a look at triangles.  We define them in the usual way — choose three points, and connect them in pairs to form three sides of a triangle.  Just like in Euclidean geometry.

Because we’re so familiar with them, I’ve drawn what would be — if we were in the Euclidean realm! — two 3-4-5 right triangles.  You’re welcome to verify that OP’Q’ would indeed be a 3-4-5 triangle in Euclidean geometry.

OK, now let’s look at these triangles from the perspective of taxicab geometry.  While we can just study these triangles by looking at the graph, it might be helpful to formally define the taxicab distance function.  If two points have coordinates $P=(x_1,y_1)$ and $Q=(x_2,y_2),$ the distance between them is defined to be

$d_T(P,Q)=|x_2-x_1|+|y_2-y_1|.$

First, a word about saying that we’re defining the distance.  That’s right — a different distance, like the one we’re used which comes from the Pythagorean theorem, would produce a different geometry.  So how your geometry “works” depends upon how you define the distance.

Second, a word about the formula.  Take a moment to convince yourself that $|x_2-x_1|$ is how far your taxicab would have to drive in an east-west direction, and $|y_2-y_1|$ is how far your taxicab would have to drive in a north-south direction.  Absolute values are needed:  the distances $d_T(P,Q)$ and $d_T(Q,P)$ should be positive and equal to each other.

Back to the triangles.  In a taxicab world, OPQ is a 3-4-7 triangle!  That might strike you as a bit unusual, since in the Euclidean world, the sum of the lengths of any two sides of a triangle is always greater than the length of the third.  This is called the triangle inequality, and is usually written

$d_E(X,Z)\le d_E(X,Y)+d_E(Y,Z)$

for points XY, and Z, where we write $d_E$ to mean the Euclidean distance.  In Euclidean geometry, the only way this inequality can actually be an equality is if Y is on the line segment whose endpoints are X and Z — and no other way.  But as we’ve just seen,

$d_T(O,Q)= d_T(O,P)+d_T(P,Q),$

where P is evidently not on the segment joining O and Q.  Yet another difference between taxicab and Euclidean geometries.

Oh, but it gets better….  In the figure above — at least in a Euclidean world — when you rotate two triangles, the angles and lengths remain the same.  In other words, the triangles are congruent.  It may seem obvious, since clearly the two triangles look the same.

What happens when we “rotate” triangle OPQ in a taxicab world?  I put “rotate” in quotes since we haven’t looked at whether or not the Euclidean idea of “angle” has a companion in the taxicab world.

If you do the calculations, you’ll see that OP’Q’ is in fact a 21/5 – 5 – 28/5 triangle!  Moreover, even though OQ was the longest side of triangle OPQ, OQ’ is not the longest side of triangle OP’Q’!  The longest side is actually OP’.

What’s going on here?  We are so used to being able to draw a triangle on a piece of paper — and certainly, if we turn our piece of paper, the lengths of the sides of the triangle don’t change!  The triangle stays exactly the same — this is the notion of congruence.  But when you change the distance function to $d_T,$ the geometry changes.  In a very fundamental way, as you see.

Essentially, we need to give up the idea of “angle” in taxicab geometry.  That might sound odd — how can you have geometry without angles?  As it turns out, there are lots of ways to do this.  We’ll be looking at this idea more as this thread continues.

And although there are differences, there are certainly things in common — such as the fact that there is a triangle inequality in both geometries.  Is this just coincidence?  Mathematically, a distance function is one which satisfies, for points X, Y, and Z:

1.  $d(X,Y) \ge 0, {\rm \ with\ equality\ only\ when\ } X=Y,$

2.  $d(X,Y)=d(Y,X), {\rm\ and}$

3.  $d(X,Z)\le d(X,Y)+d(Y,Z).$

Now we’ve already encountered properties 2 and 3 so far, and property 1 simply says that two differents points have to be separated by some positive distance.

The concept of a distance function evolved over time — whenever it made sense to talk about distance, it seemed these properties were always in play.  And in fact, the distance functions in both Euclidean and taxicab geometry have these three propertes.

So different distance functions produce different geometries.  Perhaps the hardest thing about encountering new geometries is putting aside ideas from Euclidean geometry — “forgetting” all about angles, for example, while we’re in a taxicab world.  Hopefully, as you learn about more and more non-Euclidean geometries, it will become easier and easier to navigate this Universe of diverse geometrical worlds….

## Imagifractalous! 3: Fractal Binary Trees

I’ve taken a break from Koch-like curves and p-adic sequences for an arboreal interlude….  Yes, there’s a story about why — I needed to work with Nick on a paper he was writing for Bridges — but that story isn’t quite finished yet.  When it is, I’ll tell it.  But for now, I thought I’d share some of the fascinating images we created along the way.

Let’s start with a few examples of simple binary trees.  If you want to see more, just do a quick online search — there are lots of fractal trees out there on the web!  The construction is pretty straightforward.  Start by drawing a vertical trunk of length 1.  Then, move left and right some specified angle, and draw a branch of some length r < 1.  Recursively repeat from where you left off, always adding two more smaller branches at the tip of each branch you’ve already drawn.

If you look at these two examples for a moment, you’ll get the idea.  Here, the angle used is 40 degrees, and the ratio is 5/8.  On the left, there are 5 iterations of the recursive drawing, and there are 6 iterations on the right.

Here’s another example with a lot more interaction among the branches.

This type of fractal binary tree has been studied quite a bit.  There is a well-known paper by Mandelbrot and Frame which discusses these trees, but it’s not available without paying for it.  So here is a paper by Pons which addresses the same issues, but is available online.  It’s an interesting read, but be forewarned that there’s a lot of mathematics in it!

In trying to understand various properties of these fractal trees, it’s natural to write code which creates them.  But here’s the interesting thing about writing programs like that — once they’re written, you can input anything you like!  Who says that r has to be less than 1?  The tree above is a nice example of a fractal tree with r = 1.  All the branches are of the same length, and there is a lot of overlap.  This helps create an interesting texture.

But here’s the catch.  The more iterations you go, the bigger the tree gets.  In a mathematical sense, the iterations are said to be unbounded.  But when Mathematica outputs a graphic, it is automatically scaled to fit your viewing window.  So in practice, you don’t really care how large the tree gets, since it will automatically be scaled down so the entire tree is visible.

It is important to note that when r < 1, the trees are bounded, so they are easier to study mathematically.  The paper Nick and I are working on scales unbounded trees so they are more accessible, but as I said, I’ll talk more about this in a later post.

Here are a few examples with r > 1.  Notice that as there are more and more iterations, the branches keep getting larger.  This creates a very different type of binary tree, and again, a tree which keeps getting bigger (and unbounded) as the number of iterations increases.  But as mentioned earlier, Mathematica will automatically scale an image, so these trees are easy to generate and look at.

Nick created the following image using copies of binary trees with r approximately equal to 1.04.  The ever-expanding branches allow for the creation of interesting textures you really can’t achieve when r < 1.

Another of my favorites is the following tree, created with r = 1.  The angle used, though, is 90.9 degrees.  Making the angle just slightly larger than a right angle creates an interesting visual effect.

But the exploration didn’t stop with just varying r so it could take on values 1 or greater.  I started thinking about other ways to alter the parameters used to create fractal binary trees.

For example, why does r have to stay the same at each iteration?  Well, it doesn’t!  The following image was created using values of r which alternate between iterations.

And the values of r can vary in other ways from iteration to iteration.  There is a lot more to investigate, such as generating a binary tree from any sequence of r values.  But studying these mathematically may be somewhat more difficult….

Now in a typical binary tree, the angle you branch to the left is the same as the angle you branch to the right.  Of course these two angles don’t have to be the same.  What happens if the branching angle to the left is different from the branching angle to the right?  Below is one possibility.

And for another possibility?  What if you choose two different angles, but have the computer randomly decide which is used to branch left/right at each iteration?  What then?

Here is one example, where the branching angles are 45 and 90 degrees, but which is left or right is chosen randomly (with equal probability) at each iteration.  Gives the fractal tree a funky feel….

You might have noticed that none of these images are in color.  One very practial reason is that for writing Bridges papers, you need to make sure your images look OK printed in black-and-white, since the book of conference papers is not printed in color.

But there’s another reason I didn’t include color images in this post.  Yes, I’ve got plenty…and I will share them with you later.  What I want to communicate is the amazing variety of textures available by using a simple algorithm to create binary trees.  Nick and I never imagined there would be such a fantastic range of images we could create.  But there are.  You’ve just seen them.

Once the Bridges paper is submitted, accepted (hopefully!), and revised, I’ll continue the story of our arboreal adventure.  There is a lot more to share, and it will certainly be worth the wait!