Voronoi Trees

loopspace

2018-10-22

Creative Commons License

Contents

  1. Home

  2. 1. Introduction

  3. 2. Voronoi Diagrams

  4. 3. Generalised Voronoi Diagrams

    1. 3.1. General Voronoi Diagrams

    2. 3.2. Weighted Voronoi Diagrams

    3. 3.3. Shifted Voronoi Diagrams

    4. 3.4. Shifted, Weighted Voronoi Diagrams

    5. 3.5. Ever Decreasing Circles

  5. 4. As the Duck Waddles or as the Tree Grows

1 Introduction

Figure 1: Sunlight Through a Forest Canopy

I recently saw the picture, Figure 1, of a forest canopy taken from the ground1. The light through the leaves showed definite lines where the leaves from one tree met the leaves from another. The original context in which I saw the image was about how relaxing it would be to be in the forest, looking up at the canopy.

1I have not been able to find an original source for this image. It appears to be a generic "sunlight through the leaves" image. If anyone is able to supply me with the correct attribution, I will be happy to add it here

My reaction on seeing it was to think of Voronoi Diagrams.

2 Voronoi Diagrams

Voronoi diagrams are fairly simple to understand. Start with a set of points on the plane (or piece of paper) and then divide the plane (or paper) into regions based on which point is closest.

With just two points, the dividing line is the perpendicular bisector between them, as in Figure 2.

Figure 2: Voronoi diagram for two points

With more than two points, a naive method2 of drawing the boundaries of the regions is to draw all the bisectors between the points and then figure out which parts define the regions.

2i.e., not a very good general method but fine with just a handful of points.

Figure 3: Voronoi diagram for three points

Another method, which is quite fun to watch, is to fill ever increasing circles centred at each point but to never fill in a place that's already been filled.

Anyway, back to the trees. Inspired by the picture, I wondered if anyone had used Voronoi diagrams to study tree canopies. It turned out that they had (many thanks to the people on twitter who pointed me in this direction). The phenomenon whereby the boundaries are visible is called canopy shyness and some papers have been written using Voronoi diagrams as a tool to study this.

3 Generalised Voronoi Diagrams

Full confession: I've not yet read the papers. I need to set aside time to read them, particularly as I suspect they won't be aimed at me (a Mathematician) so I'll have a bit of translation to do when reading them. Nevertheless, it's still an interesting topic and, as usual, it sparked me off on a little mathematical journey of my own which, in all likelihood, has no particular relevance to tree growth but which is nevertheless inspired by it.

One thing that particularly struck me about the original image was how well-defined and above all straight the gaps were. On the face of it, this seems reasonable: the branches from each tree grow outward until they get near to a space already occupied by the branches from another tree. This is exactly the situation that Voronoi diagrams describe.

But that assumes two things: that the trees all grow at the same speed and that they started at the same time.

What if we relax those conditions?

3.1 General Voronoi Diagrams

Before looking at what happens if the trees grow at different speeds and at different times, let's examine the general case to establish some notation.

We suppose that we have some points in the plane, say {ai}, and each is a source of growth. We additionally assume that the growth is defined by a radial function, say ri(t), in that the unfettered growth from ai at time t is a circle of radius ri(t).

Each function ri(t) has the structure that there is some time ti such that ri(t) is zero for t<ti, and for t>ti then it is strictly increasing. This means that once the growth starts, the function from time to radius is invertible – i.e., knowing the radius we can (in theory) figure out the time it got there.

By "unfettered growth" I mean that the growth if no obstruction were present.

For a point x, to figure out which source gets to x we need to look at the distances from x to each point ai. This is done using the Euclidean distance function, written x-ai2, which is none other than Pythagoras' theorem in disguise. For each point, we can then work out the time at which ri(t)=x-ai2 which would be the time when the growth from ai would reach x. The earliest time "wins".

Since we've assumed that ri(t) is invertible (at least for t>ti), these times are given by:

tx,i=ri-1(x-ai2)

To find the boundary between two regions, we need to figure out those points x which are reached from two source points, say a1 and a2, at the same time. This means that we need to find x such that tx,1=tx,2, which means solving:

r1-1(x-a12)=r2-1(x-a22)

In the next sections I'll look at this equation for particular circumstances. As those circumstances get more complicated, I'll be able to say less in general. To counteract that, here's a Voronoi playground. It places a number of points in a square and generates the Voronoi diagram. You can move the points around. You can choose one of the types of Voronoi diagram referred to below, if there are any parameters then it generates them randomly within a reasonable range.

3.2 Weighted Voronoi Diagrams

The easiest one to work with is if the trees grow at different speeds. Each tree, located at point ai, has a speed, say si, such that its unfettered growth function is given by:

ri(t)={0t0sitt>0

Thus the boundaries between two regions are those x for which:

1six-ai2=1sjx-aj2

Rearranging this, say for a1 and a2, produces an equation of the form:

x-a12=kx-a22

where k is some (positive) constant. This is a circle.

Such Voronoi diagrams are called weighted Voronoi diagrams. The boundaries are made up from arcs of circles, as in Figure 4.

Figure 4: Weighted Voronoi Diagram

3.3 Shifted Voronoi Diagrams

The second possible change would be to have the trees start growing at different times, say at time ti from point ai, but at the same speed. The unfettered growth function would then be of the form

ri(t)={0ttit-tit>ti

Thus the boundaries between two regions is given by finding x such that:

x-ai2+ti=x-aj2+tj

This rearranges to an equation of the form, for a1 and a2:

x-a12=x-a22+k

where k can be any real number3.

3It is worth noting that if k is larger than the distance between the points, the point that starts will totally dominate the plane.

This is the focus–focus property of a hyperbola4. Thus in this case the boundaries of the Voronoi regions will be segments of hyperbolae, as in Figure 5.

4In full confession mode, I should say that I expanded out the equation to get to the hyperbola before I realised this.

Figure 5: Shifted Voronoi Diagram

3.4 Shifted, Weighted Voronoi Diagrams

We're doing quite well with conic sections here, but sadly all good things come to an end. If we allow both shifting and weighting then we get equations of degree 4.

Our unfettered growth functions now look like:

ri(t)={0ttisi(t-ti)t>ti

and this means that we are solving equations of the form:

1six-ai2+ti=1sjx-aj2+tj

which rearranges to something of the form:

x-a12=kx-a22+c

To see what this looks like, let us transform the points so that a1 and a2 lie on the x–axis, say at (-1,0) and (1,0).

Our equation is thus:

(x,y)-(-1,0)2=k(x,y)-(1,0)2+c

Squaring both sides, we can replace the 2 by the Pythagorean identity:

(x+1)2+y2=k2(x-1)2+k2y2+2kc(x,y)-(1,0)2+c2

Expanding out the brackets and gathering terms, we get:

(1-k2)x2+2(k2+1)x+(1-k2)y2+(1+k2+c2)=2kc(x,y)-(1,0)2

To see the "wood for the trees5", let's hide some of the mess and write this as:

5You didn't think I'd go through this whole thing and not write that, did you?

α1x2+α2x+α3y2+α4=α5(x,y)-(1,0)2

The 2 part is secretly a square root, so we square both sides again to get:

α12x4+α22x2+α32y4+α42+2(α1α2x3+α1α3x2y2+α1α4x2+α2α3xy2+α2α4x+α3α4y2)=α52((x-1)2+y2)=α52x2-2α52x+α52+α52y2

Gathering everything together, and relabelling again, the general form is:

p4,0x4+p3,0x3+p2,0x2+p1,0x+p0,4y4+p0,2y2+p2,2x2y2+p1,2xy2+p0,0=0

which is a quartic. This means that the boundaries of the regions in the Voronoi diagram could be quite complicated, as in Figure 6.

Figure 6: Voronoi Diagram with Weights and Shifts

3.5 Ever Decreasing Circles

Back to thinking about trees, I do think that the unfettered growth model has its flaws. A tree with no competitors would not spread out indefinitely. Most likely, there would be some maximum spread and that as it reached that distance, the growth would gradually slow. A possibly model for this would be:

ri(t)={0ttiMi(1-e-ki(t-ti))

The inverse of this function (for t>ti) is given by:

ri-1(x)=-1kilog(1-xMi)+ti

This isn't actually as scary as it looks. In particular, if all the Mi are the same, say M, then this is of the form:

ri-1(x)=1kig(x)+ti

where g(x)=-log(1-xM). This looks like the shifted, weighted Voronoi diagram but with a different notion of what distance is, as in Figure 7.

Figure 7: Voronoi Diagram with Exponential Growth Function

4 As the Duck Waddles or as the Tree Grows

I'll end with a comment on where I can see a limitation of Voronoi diagrams as I've described them above. It is entirely possible that this is known about, and dealt with, in the literature but as that's still on my "to read" list then I don't know.

Let's go back to the weighted Voronoi diagram and consider the situation with two points. The Voronoi diagram looks a little like Figure 8.

Figure 8: Weighted Voronoi Diagram with Two Points

Now the diagram shows the plane divided into two regions. These two regions are defined by which duck would reach a point first (clearly the superhero duck would be faster than the duck with the ball and chain).

But here's the thing: to get to some of those points first, the superhero duck would have to fly through the region that the prison duck controls. That is, the criteria for "getting there first" is by the most direct route.

With trees, that route might not be available. If the slower growing tree has filled a region then the faster one won't send branches through it to reach the other side, it will have to go around. So the actual shape won't be a circle, but will extend somewhat to (in this case) the right-hand side. Possibly more of the shape in Figure 9.

Figure 9: Tree-like Voronoi Diagram with Two Points

In this case, the metric used to measure the distance between two points will be the path metric which measures it by the length of the shortest path. Normally this agrees with the Euclidean metric, but when there are excluded regions then it can be more complicated.

Something to investigate!