The End 2016 Mathematics A To Z: Voronoi Diagram

This is one I never heard of before grad school. And not my first year in grad school either; I was pretty well past the point I should’ve been out of grad school before I remember hearing of it, somehow. I can’t explain that.

Voronoi Diagram.

Take a sheet of paper. Draw two dots on it. Anywhere you like. It’s your paper. But here’s the obvious thing: you can divide the paper into the parts of it that are nearer to the first, or that are nearer to the second. Yes, yes, I see you saying there’s also a line that’s exactly the same distance between the two and shouldn’t that be a third part? Fine, go ahead. We’ll be drawing that in anyway. But here we’ve got a piece of paper and two dots and this line dividing it into two chunks.

Now drop in a third point. Now every point on your paper might be closer to the first, or closer to the second, or closer to the third. Or, yeah, it might be on an edge equidistant between two of those points. Maybe even equidistant to all three points. It’s not guaranteed there is such a “triple point”, but if you weren’t picking points to cause trouble there probably is. You get the page divided up into three regions that you say are coming together in a triangle before realizing that no, it’s a Y intersection. Or else the regions are three strips and they don’t come together at all.

What if you have four points … You should get four regions. They might all come together in one grand intersection. Or they might come together at weird angles, two and three regions touching each other. You might get a weird one where there’s a triangle in the center and three regions that go off to the edge of the paper. Or all sorts of fun little abstract flag icons, maybe. It’s hard to say. If we had, say, 26 points all sorts of weird things could happen.

These weird things are Voronoi Diagrams. They’re a partition of some surface. Usually it’s a plane or some well-behaved subset of the plane like a sheet of paper. The partitioning is into polygons. Exactly one of the points you start with is inside each of the polygons. And everything else inside that polygon is nearer to its one contained starting point than it is any other point. All you need for the diagram are your original points and the edges dividing spots between them. But the thing begs to be colored. Give in to it and you have your own, abstract, stained-glass window pattern. So I’m glad to give you some useful mathematics to play with.

Voronoi diagrams turn up naturally whenever you want to divide up space by the shortest route to get something. Sometimes this is literally so. For example, a radio picking up two FM signals will switch to the stronger of the two. That’s what the superheterodyne does. If the two signals are transmitted with equal strength, then the receiver will pick up on whichever the nearer signal is. And unless the other mathematicians who’ve talked about this were just as misinformed, cell phones pick which signal tower to communicate with by which one has the stronger signal. If you could look at what tower your cell phone communicates with as you move around, you would produce a Voronoi diagram of cell phone towers in your area.

Mathematicians hoping to get credit for a good thing may also bring up Dr John Snow’s famous halting of an 1854 cholera epidemic in London. He did this by tracking cholera outbreaks and measuring their proximity to public water pumps. He shut down the water pump at the center of the severest outbreak and the epidemic soon stopped. One could claim this as a triumph for Voronoi diagrams, although Snow can not have had this tool in mind. Georgy Voronoy (yes, the spelling isn’t consistent. Fashions in transliterating Eastern European names — Voronoy was Ukrainian and worked in Warsaw when Poland was part of the Russian Empire — have changed over the years) wasn’t even born until 1868. And it doesn’t require great mathematical insight to look for the things an infected population has in common. But mathematicians need some tales of heroism too. And it isn’t as though we’ve run out of epidemics with sources that need tracking down.

Voronoi diagrams turned out to be useful in my own meager research. I needed to model the flow of a fluid over a whole planet, but could only do so with a modest number of points to represent the whole thing. Scattering points over the planet was easy enough. To represent the fluid over the whole planet as a collection of single values at a couple hundred points required this Voronoi-diagram type division. … Well, it used them anyway. I suppose there might have been other ways. But I’d just learned about them and was happy to find a reason to use them. Anyway, this is the sort of technique often used to turn information about a single point into approximate information about a region.

(And I discover some amusing connections here. Voronoy’s thesis advisor was Andrey Markov, who’s the person being named by “Markov Chains”. You know those as those predictive-word things that are kind of amusing for a while. Markov Chains were part of the tool I used to scatter points over the whole planet. Also, Voronoy’s thesis was On A Generalization Of A Continuous Fraction, so, hi, Gaurish! … And one of Voronoy’s doctoral students was Wacław Sierpiński, famous for fractals and normal numbers.)

Voronoi diagrams have a lot of beauty to them. Some of it is subtle. Take a point inside its polygon and look to a neighboring polygon. Where is the representative point inside that neighbor polygon? … There’s only one place it can be. It’s got to be exactly as far as the original point is from the edge between them, and it’s got to be on the direction perpendicular to the edge between them. It’s where you’d see the reflection of the original point if the border between them were a mirror. And that has to apply to all the polygons and their neighbors.

From there it’s a short step to wondering: imagine you knew the edges. The mirrors. But you don’t know the original points. Could you figure out where the representative points must be to fit that diagram? … Or at least some points where they may be? This is the inverse problem, and it’s how I first encountered them. This inverse problem allows nice stuff like algorithm compression. Remember my description of the result of a Voronoi diagram being a stained glass window image? There’s no reason a stained glass image can’t be quite good, if we have enough points and enough gradations of color. And storing a bunch of points and the color for the region is probably less demanding than storing the color information for every point in the original image.

If we want images. Many kinds of data turn out to work pretty much like pictures, set up right.

The Equidistribution of Lattice Shapes of Rings: A Friendly Thesis

I can't tell you how excited I am to see a Princeton math PhD thesis that starts like this.https://t.co/O5Ep59HblE pic.twitter.com/3GAzfThdPI

— Federico Ardila (@FedericoArdila) December 8, 2015

So, you’re never going to read my doctoral thesis. That’s fair enough. Few people are ever going to, and even the parts that got turned into papers or textbooks are going to attract few readers. They’re meant for people interested in a particular problem that I never expected most people to find interesting. I’m at ease with that. I wrote for an audience I expected knew nearly all the relevant background, and that was used to reading professional, research-level mathematics. But I knew that the non-mathematics-PhDs in my life would look at it and say they only understood the word ‘the’ on the title page. Even if they could understand more, they wouldn’t try.

Dr Piper Alexis Harron tried meeting normal folks halfway. She took her research, and the incredible frustrations of doing that research — doctoral research is hard, and is almost as much an endurance test as anything else — and wrote what she first meant to be “a grenade launched at my ex-prison”. This turned into something more exotic. It’s a thesis “written for those who do not feel that they are encouraged to be themselves”, people who “don’t do math the `right way’ but could still greatly contribute to the community”.

The result is certainly the most interesting mathematical academic writing I’ve run across. It’s written on several levels, including one meant for people who have heard of mathematics certainly but don’t partake in the stuff themselves. It’s exciting reading and I hope you give it a try. It may not be to your tastes — I’m wary of words like ‘laysplanation’ — but it isn’t going to be boring. And Dr Harron’s secondary thesis, that mathematicians need to more aggressively welcome people into the fold, is certainly right.

You’re not missing anything by not reading my thesis. Although my thesis defense offered the amusing sidelight that the campus’s albino squirrel got into the building. My father and some of the grad student friends of mine were trying without anything approaching success to catch it. I’m still not sure why they thought the squirrel needed handling by them.

The Set Tour, Part 10: Lots of Spheres

The next exhibit on the Set Tour here builds on a couple of the previous ones. First is the set Sⁿ, that is, the surface of a hypersphere in n+1 dimensions. Second is Bⁿ, the ball — the interior — of a hypersphere in n dimensions. Yeah, it bugs me too that Sⁿ isn’t the surface of Bⁿ. But it’d be too much work to change things now. The third has lurked implicitly since all the way back to Rⁿ, a set of n real numbers for which the ordering of the numbers matters. (That is, that the set of numbers 2, 3 probably means something different than the set 3, 2.) And fourth is a bit of writing we picked up with matrices. The selection is also dubiously relevant to my own thesis from back in the day.

S^{n x m} and B^{n x m}

Here ‘n’ and ‘m’ are whole numbers, and I’m not saying which ones because I don’t need to tie myself down. Just as with Rⁿ and with matrices this is a whole family of sets. Each different pair of n and m gives us a different set S^{n x m} or B^{n x m}, but they’ll all look quite similar.

The multiplication symbol here is a kind of multiplication, just as it was in matrices. That kind is called a “direct product”. What we mean by S^{n x m} is that we have a collection of items. We have the number m of them. Each one of those items is in Sⁿ. That’s the surface of the hypersphere in n+1 dimensions. And we want to keep track of the order of things; we can’t swap items around and suppose they mean the same thing.

So suppose I write S^{2 x 7}. This is an ordered collection of seven items, every one of which is on the surface of a three-dimensional sphere. That is, it’s the location of seven spots on the surface of the Earth. S^{2 x 8} offers similar prospects for talking about the location of eight spots.

With that written out, you should have a guess what B^{n x m} means. Your guess is correct. It’s a collection of m things, each of them within the interior of the n-dimensional ball.

Now the dubious relevance to my thesis. My problem was modeling a specific layer of planetary atmospheres. The model used for this was to pretend the atmosphere was made up of some large number of vortices, of whirlpools. Just like you see in the water when you slide your hand through the water and watch the little whirlpools behind you. The winds could be worked out as the sum of the winds produced by all these little vortices.

In the model, each of these vortices was confined to a single distance from the center of the planet. That’s close enough to true for planetary atmospheres. A layer in the atmosphere is not thick at all, compared to the planet. So every one of these vortices could be represented as a point in S², the surface of a three-dimensional sphere. There would be some large number of these points. Most of my work used a nice round 256 points. So my model of a planetary atmosphere represented the system as a point in the domain S^{2 x 256}. I was particularly interested in the energy of this set of 256 vortices. That was a function which had, as its domain, S^{2 x 256}, and as range, the real numbers R.

But the connection to my actual work is dubious. I was doing numerical work, for the most part. I don’t think my advisor or I ever wrote S^{2 x 256} or anything like that when working out what I ought to do, much less what I actually did. Had I done a more analytic thesis I’d surely have needed to name this set. But I didn’t. It was lurking there behind my work nevertheless.

The energy of this system of vortices looked a lot like the potential energy for a bunch of planets attracting each other gravitationally, or like point charges repelling each other electrically. We work it out by looking at each pair of vortices. Work out the potential energy of those two vortices being that strong and that far apart. We call that a pairwise interaction. Then add up all the pairwise interactions. That’s it. [1] The pairwise interaction is stronger as each vortex is stronger; it gets weaker as the vortices get farther apart.

In gravity or electricity problems the strength falls off as the reciprocal of the distance between points. In vortices, the strength falls off as minus one times the logarithm of the distance between points. That’s a difference, and it meant that a lot of analytical results known for electric charges didn’t apply to my problem exactly. That was all right. I didn’t need many. But it does mean that I was fibbing up above, when I said I was working with S^{2 x 256}. Pause a moment. Do you see what the fib was?

I’ll put what would otherwise be a footnote here so folks have a harder time reading right through to the answer.

[1] Physics majors may be saying something like: “wait, I see how this would be the potential energy of these 256 vortices, but where’s the kinetic energy?” The answer is, there is none. It’s all potential energy. The dynamics of point vortices are weird. I didn’t have enough grounding in mechanics when I went into them.

That’s all to the footnote.

Here’s where the fib comes in. If I’m really picking sets of vortices from all of the set S^{2 x 256}, then, can two of them be in the exact same place? Sure they can. Why couldn’t they? For precedent, consider R³. In the three-dimensional vectors I can have the first and third numbers “overlap” and have the same value: (1, 2, 1) is a perfectly good vector. Why would that be different for an ordered set of points on the surface of the sphere? Why can’t vortex 1 and vortex 3 happen to have the same value in S²?

The problem is if two vortices were in the exact same position then the energy would be infinitely large. That’s not unique to vortices. It would be true for masses and gravity, or electric charges, if they were brought perfectly on top of each other. Infinitely large energies are a problem. We really don’t want to deal with them.

We could deal with this by pretending it doesn’t happen. Imagine if you dropped 256 poker chips across the whole surface of the Earth. Would you expect any two to be on top of each other? Would you expect two to be exactly and perfectly on top of each other, neither one even slightly overhanging the other? That’s so unlikely you could safely ignore it, for the same reason you could ignore the chance you’ll toss a coin and have it come up tails 56 times in a row.

And if you were interested in modeling the vortices moving it would be incredibly unlikely to have one vortex collide with another. They’d circle around each other, very fast, almost certainly. So ignoring the problem is defensible in this case.

Or we could be proper and responsible and say, “no overlaps” and “no collisions”. We would define some set that represents “all the possible overlaps and arrangements that give us a collision”. Then we’d say we’re looking at S^{2 x 256} except for those. I don’t think there’s a standard convention for “all the possible overlaps and collisions”, but Ω is a reasonable choice. Then our domain would be S^{2 x 256} \ Ω. The backslash means “except for the stuff after this”. This might seem unsatisfying. We don’t explicitly say what combinations we’re excluding. But go ahead and try listing all the combinations that would produce trouble. Try something simple, like S^{2 x 4}. This is why we hide all the complicated stuff under a couple ordinary sentences.

It’s not hard to describe “no overlaps” mathematically. (You would say something like “vortex number j and vortex number k are not at the same position”, with maybe a rider of “unless j and k are the same number”. Or you’d put it in symbols that mean the same thing.) “No collisions” is harder. For gravity or electric charge problems we can describe at least some of them. And I realize now I’m not sure if there is an easy way to describe vortices that collide. I have difficulty imagining how they might, since vortices that are close to one another are pushing each other sideways quite intently. I don’t think that I can say they can’t, though. Not without more thought.