The Joy of Barycentric Subdivision

We shall be interested in what happens to the shapes of the triangles one gets by subdividing a large number of times. ...

Bill Casselman
University of British Columbia, Vancouver, Canada
Email Bill Casselman

Introduction

Even nowadays, when so much mathematical territory has already been well explored, interesting and apparently new mathematical phenomena can arise in very simple circumstances.

The barycenter of a triangle is its center of gravity. It can be found easily by a simple geometric construction. Draw a line from each vertex to the midpoint of the opposite side. Euclid knew that these three lines meet in a single point, and this turns out to be what we call the triangle's barycenter.

A basic fact is that the length of the blue line is twice that of the red one.

The construction of the barycenter produces a subdivision of the original triangle into six smaller triangles. I'll call the original triangle the parent, and these the children. What can we say about the children, compared to their parent?

The only thing that is easy to prove is that they are definitely smaller. The diameter of a triangle is the length of its longest side. It is not too difficult to show that the diameter of any of the children is less than $2/3$ that of the parent. This bound is sharp, in the sense that one can find a sequence of parents degenerating into a line segment for which the diameters of some children approaches $2/3$ that of the parent.

There may be interesting things to be said about how the sizes of children vary, but we are going to be interested only in the shapes, rather than the sizes, of children. More precisely, we shall be interested in what happens to the shapes of the triangles one gets by subdividing a large number of times.

 
  Original triangle After one subdivision
 
  After two subdivisions After three subdivisions

 

One's first impression is that the triangles become more and more pinched---thinner, one might say---as subdivision proceeds. But a close look shows that this is not quite the case---most of the triangles after 3 subdivisions are fairly thin, but there are a few that are not so thin.

How can we describe what is going on? The answer will be in statistical terms. But in order to analyze what happens statistically, we need a precise way to specify the shape of a triangle.

What is the shape of a triangle?

Before we continue, I have to explain more about what we mean by the shape of a triangle. When do two triangles have the same shape? Is it possible to say that two triangles have nearly the same shape, or very different shapes?

Two triangles are said to be similar if they are the same up to a scale change. In this case, they certainly have the same shape. But I'll also say they have the same shape if one is the mirror image of the other. (This is a somewhat arbitrary convention, but common enough.) The following triangles have, in this sense, the same shape.

But now we can find a standard model of any triangle, so as to be able to compare shapes. Given a triangle, first scale it so that its longest side has length one. Then rotate it so its longest side is horizontal. Rotate it again (by $180^{\circ}$) if necessary so the triangle is on top of its longest side. Flip it around a vertical axis, if necessary, so that its shortest side is at the left. The triangle we are now looking at is very special: $\bullet$ its bottom side is a horizontal segment of length $1$ (because we have scaled it suitably); $\bullet$ its top vertex lies at distance at most one from its right hand vertex (because the right side is at most as long as the bottom); and $\bullet$ the top vertex lies to the left of the center of the bottom (because of our convention regarding mirror images). If we are given a coordinate system, we may even place the bottom to be the segment from $(0,0)$ to $(1,0)$. In this way, every triangle is associated to a triangle of a very special type---one that looks like this:

 

Such a triangle is completely determined by its top vertex, which lies in the region I'll call $\Sigma$ which is colored gray in the figure above. Thus we can say that two triangles have nearly the same shape if the corresponding points of $\Sigma$ are close.

The top of the region $\Sigma$ corresponds to an equilateral triangle, points on the arc at the left or the vertical line at the right are all isosceles triangles, and points towards the bottom are all rather flat. Points of the bottom correspond to degenerate or flat triangles, all of whose vertices lie on a line.

Eventually I'll want to refer to the triangles in a subdivision, and I assign labels in a somewhat arbitrary fashion as shown here:

Comments?

Statistics

We can now visualize in an instructive way the process of barycentric subdivision. We start with a given triangle, and plot the point of the region $\Sigma$ corresponding to it. When we subdivide, we get $6$ new points of $\Sigma$. If we again subdivide each of these, we get all together $36$ points of $\Sigma$. In the following figures, I started with a triangle whose vertices were $(0,0)$, $(1,0)$, and $(1/4,1/2)$. The last figure records its $6^{8} = 1,679,616$ descendants after $8$ subdivisions.

These figures exhibit a number of interesting features.

  • First of all, it appears that as time goes on the descendants of the original triangle fill out the region $\Sigma$. In other words, the descendants approximate eventually any arbitrary shape. This has been proved rigorously, in what I believe to be the first mathematical paper to discuss barycentric subdivisions:

    Theorem. (Barany et al.) Successive barycentric subdivisions of a non-degenerate triangle can approximate any given triangular shape.

  • But the density of descendants is not uniform, nor does it remain essentially the same as subdivision proceeds. Instead, there seems to be a kind of flow towards the bottom of $\Sigma$. We'll look at this phenomenon in detail later on.
     
  • One of the more curious features are the patterns of arcs of circles along the bottom. These are particularly evident at lower left and right.

    These arcs are also apparent, although more weakly, along all of the bottom. This is, as far as I know, a kind of resonance about which nothing---absolutely nothing---is known. We seem to be entering completely new mathematical country.

  • The bottom in each figure also shows a kind of dead zone in which no triangles are evident. This zone shrinks as the number of subdivisions increases. I do not know that anyone has remarked on this, but it ought not to be difficult to explain, and rather precisely.

    The drift to the south

    Let's look again at the apparent flow downwards in successive subdivisions. The images above don't show this very well, because the points recording subdivision triangles achieve saturation. But there are other ways to make it more apparent. The following figure is almost the same as one we have seen previously, but now the bar graph on the right side records the proportion in corresponding horizontal slices.

     

    There ought to be no need to reproduce the point plots, so the following figures just exhibit the bar graphs:

    These should make it much clearer that as the number of subdivisions increases, there is a flow towards the bottom. The impression is reinforced by the following table showing the means of the distributions: $$ \eqalignno { \hbox{Number of subdivisions:} & & \; 0 & \quad 1 & \quad 2 & \quad 3 & \quad 4 & \quad 5 & \quad 6 & \quad 7 &\quad 8 & \quad 9 & \quad 10 \cr \hbox{Mean height:} & & 0.5 & 0.3683 & 0.3136 & 0.2656 & 0.2296 & 0.2013 & 0.1781 & 0.1588 & 0.1425 & 0.1285 & 0.1163 \cr } $$

    These form an approximate geometric sequence with ratio $q \sim 0.906 = e^{-0.099}$.

    This flow, at least, is partly understood, although in terms we haven't yet seen. Corresponding to the barycentric subdivision of triangles is a kind of random walk among the shapes of triangles. Start with a triangle $T_{0}$, and suppose $S_{1}$, ... , $S_{6}$ are the triangles you get by subdividing it. Toss a die. If the face marked $i$ appears, let $T_{1} = S_{i}$. If we do this repeatedly, we get a sequence of triangles $T_{m}$ in which $T_{m+1}$ is a random choice among the subdivisions of $T_{m}$. If I plot for each the corresponding point of the region $\Sigma$, I get a path in $\Sigma$. Here, for example, is what I get if I start with the same triangle $T_{0}$ whose vertices are $(0,0)$, $(1,0)$, $(1/4, 1/2)$:

    There are occasional bounces up, but the trend is towards the bottom. This is the way things usually go, as has also been proved rigorously by Barany et al.:

    Theorem. (Barany et al.) A random walk among successive barycentric subdivisions of a triangle will almost certainly converge to flat triangles.

    Empirically, one sees that as subdivision proceeds the shapes pile up along the bottom of $\Sigma$. This observation can be made more precise. Barycentric subdivision can be applied even to flat triangles, and produces other flat triangles. In order to understand the shapes that barycentric subdivision generates it is important to understand how it works for flat triangles.

    There are therefore two reasons flat triangles are important. One is that under barycentric subdivision, triangles that are nearly flat behave approximately as if they were flat, and in particular all the triangles they divide into are also fairly flat. Another is that arbitrary triangles tend to become flatter and flatter after many subdivisions.

    Consistently with the last theorem, the amount a child can bounce above its parent is rather limited. I have already mentioned that if a triangle is nearly flat, its children are also nearly flat. Given this, one might wonder if the triangles you see eventually converge to a fixed flat triangle. This is not, however, what you'd guess from the figure. In fact, what happens is the opposite: as the shapes become flatter and flatter, they traverse somewhat randomly in a horizontal direction. This has been discussed in some detail in the work of Diaconis and Miclo. Not only does barycentric subdivision make sense for flat triangles, but---as we shall see in a later section---it is simpler to understand than for non-degenerate triangles. In addition, Diaconis and Miclo prove that triangles that are nearly flat behave much like flat ones.

    The barycentric subdivision of flat triangles is all by itself an interesting business, and quite different from what we have seen so far. The basic fact is that subdivision of a flat triangle produces more flat triangles. So we can apply to it much the same process that we did to real triangles. We start with some initial value of $x$, then compute successively all children of current values of $x$.

    One could illustrate this as I illustrated the barycentric subdivisions of a given starting flat triangle. But this would not be so illuminating, since the interval $[0,1/2]$ simply fills up rapidly. There is no flow, but instead a gradual saturation. This is a proven fact: as time goes on, what we see is that the distribution of descendants approximates better and better a fixed density. (The technical way to phrase this is to say that the process is ergodic.) This also has been proved by Diaconis and Miclo, who prove in addition a few more properties of this density. In the following figure, one sees the approximate density after many subdivisions.

    It seems to be at least continuous, although this has not been verified rigourously. How smooth is it?

    Comments?

    More about flat triangles

    I have said that the analysis of Diaconis and Micro is based upon a close examination of what happens in the subdivision of flat triangles. This is relatively simple from both a theoretical and a practical standpoint, and I will say something about that in this section.

    One convenient thing about flat triangles is that we can see extremely explicitly how subdivision works. Every flat triangle corresponds to a point $(x,0)$ on the bottom of the region $\Sigma$, with $0 \le x \le 1/2$. The following figure will suggest what the "triangles" in the subdivision are.

    A flat triangle is a set of three points, not all the same, in a line. One can transform a flat triangle so that its vertices are $(0,0)$, $(1,0)$, $(x,0)$ with $0 \le x \le 1/2$ - i.e. so that $x$ is on the bottom of $\Sigma$. Using labeling introduced earlier, the figure should help you see that the vertices of the barycentric subdivision are: $$ \eqalignno { \Delta_{1} &\colon 1/2 & 1/2 - (x+1)/3 & (x+1)/3 \cr \Delta_{2} &\colon 1 -(x+1)/3 & 1/2 - (x+1)/3 & 1/2 \cr \Delta_{3} &\colon 1-(x+1)/3 & 1- (x+1)/2 & (x+1)/2 - (x+1)/3 \cr \Delta_{4} &\colon (x+1)/2 - x & (x+1)/3 - x & (x+1)/2 - (x+1)/3 \cr \Delta_{5} &\colon (x+1)/3 - x/2 & (x+1)/3 - x & x/2 \cr \Delta_{6} &\colon (x+1)/3 & (x+1)/3 - x/2 & x/2 \cr } $$

    For $0 \le x \le 1/2$ all of these are non-negative, and in every case the first is the longest "side" (which is therefore the sum of the other two). Which is the shortest side is not the same for all. The point of $\Sigma$ corresponding to each of these turns out to be $$ \eqalign { \Delta_{1} &\colon \; { 1 - 2x \over 3 } \cr \Delta_{2} &\colon \; { 1 - 2x \over 4 - 2x } \cr \Delta_{3} &\colon \; { 1 + x \over 4 - 2x } \cr \Delta_{4} &\colon \; { 1 + x \over 3 - 3x } \quad (x < 1/5) \cr & \phantom{\colon} \;\> {2 - 4x \over 3 - 3x } \quad (x \ge 1/5) \cr \Delta_{5} &\colon \;\> { 3x \over 2 - x } \>\quad (x < 2/7) \cr & \phantom{\colon} \;\> {2 - 4x \over 2 - x } \quad (x \ge 2/7) \cr \Delta_{6} &\colon \;\> { 3 \over 2 + 2x } \cr } $$

    We can see how this works out by plotting the quantities in these columns as a function of $x$ over the range $[0, 1/2]$. For example, let's look at $\Delta_{5}$. Here are graphs of the "sides" of $\Delta_{5}$, plotted as a function of $x$ in the range $[0,1/2]$:

     

    Thus the third column is smallest in the range $[0, 2/7]$, and second in the rest.

    These explicit values make it relatively simple to see what is going on for flat triangles. To each $i = 1$, ... , $6$ we have a map from $[0,1/2]$ to itself, and these are graphed in the following figure:

    Final remarks

    A number of things about the shapes one gets by barycentric subdivision of a triangle have been proven, but some of the most interesting questions do not seem even to have been approached. Here are a few that stand out:

    • Are the circles one sees an artefact, or is there an interesting explanation of them? As far as I can tell, they are a completely new phenomenon.
    • The shapes form a kind of wave flowing down to the bottom of $\Sigma$. Can one find explicitly the asymptotic form of this wave? I am not familiar with anything like this in the current mathematical literature. What one might hope is that what we are seeing here is a kind of universal process, a dynamic analogue of the central limit theorem, which explains why the normal curve is ubiquitous. Of course the answer will depend on the form of the stable distribution on the flat triangles.
    • Are there other examples of similar probabilistic flows?

    I haven't said anything about how the known facts have been proved. The common technique in all cases is a clever transformation of the random walk to a question concerning the product of random $2 \times 2$ matrices, about which a lot has been known for a long time. I do not see, however, how this technique could tell us anything about the problems posed above.

    Comments?

    Reading further

    There is not much literature on this topic, and---as far as I can tell---nothing except research publications.
    • Amie Wilkinson, `What are Lyapunov exponents, and why are they interesting?', Bulletin of the American Mathematical Society 54, pages 79-106.

      It was this article that brought to my attention the problems of barycentric subdivision. The Lyapunov exponent in play here is the logarithm specifying the geometric progression of means mentioned above.

    • Bob Hough, `Tessellation of a triangle by repeated barycentric subdivision', Electronic Communications in Probability 14 (2015), 270-277.
       
    • Imre Barany, Alan F. Beardon, T. K. Carne, `Barycentric subdivision of triangles and semigroups of Möbius maps', Mathematika 43 (1996), 165-171.

      This is, I believe, the first investigation of the dynamics of barycentric subdivision.

    • Persi Diaconis and Laurent Miclo, `On barycentric subdivision, with simulations'.

      This is the most thorough investigation in the literature.

    • Child plot animation. A file that I have made illustrating through `page turning animation' how the formation of children behaves for different points of $\Sigma$. Keep in mind when looking at it that the graph of any transformation from 2D to 2D sits in 4D, and hence illustration is intrinsically difficult for humans.

    Acknowledgement

    I have benefited greatly from discussions with my colleague Gordon Slade.

    Comments?

    Bill Casselman
    University of British Columbia, Vancouver, Canada
    Email Bill Casselman