A Tournament

2015-04-24
interests: math, graph theory

A tournament is a set of nodes in which each pair of nodes $a,b$ has exactly one edge between them: either $a\sim b$ or $b\sim a$ . In tournament terms, either player $a$ beats $b$ or $b$ beats $a$ . Let's make a tournament where each player $i$ picks an angle $\psi_i$ , where $\psi_i$ beats $\psi_j$ if $\psi_j$ is counterclockwise from $\psi_i$ :

diagram of phi 1 beating angles on the circle clockwise (up to 180 degrees) to it and losing to angles counterclockwise from it

If $\psi_i$ beats $\psi_j$ , we say $\psi_i\sim \psi_j$ . This tournament has some neat properties:

If there is any cycle $\psi_1\sim \psi_2\sim\ldots \sim \psi_n\sim \psi_1$ , then it has a subcycle $\psi_1\sim \psi_i\sim\psi_j \sim \psi_1$ of length 3.
The tournament has a cycle if and only if each angle beats at least one other angle. From another perspective, there is a cycle as long as the angles do not all lie on one half of the circle.

Using these and some cool facts from my previous post, we can find a set of 3 points on a sphere to use for interpolation at another given point. What the hell?

What?

Here's what this tournament looks like. Each point (other than the center) is an angle, and each arrow represents one angle beating another.

4 points on a circle with a directed graph between each pair of points indicating which one wins

My first claim above states that for any cycle, such as, $\psi_1\sim\psi_2\sim\psi_3\sim\psi_4\sim \psi_1$ , there is a shorter subcycle. In this case one such subcycle is $\psi_1\sim\psi_3\sim\psi_4\sim\psi_1$ .

My second claim says that since this tournament contains a cycle, there is no angle which beats every other angle. Each angle has at least one arrow pointing to it, so this holds true.

First Claim: every cycle has a subcycle of length 3

Let's first argue that any cycle has a subcycle of length 3. Suppose the cycle $\psi_1\sim\psi_2\sim\ldots \psi_n\sim\psi_1$ has length $n\ge4$ . If the cycle does multiple revolutions, then it must pass over $\psi_1$ at least once; it jumps from some $\psi_i$ to $\psi_{i+1}$ where $\psi_i$ is clockwise from $\psi_1$ and $\psi_{i+1}$ is couterclockwise from it. Then we know that $\psi_1\sim\psi_2\sim\ldots \psi_i\sim\psi_1$ is a shorter subcycle.

On the other hand, if the cycle does only one revolution, then consider each consecutive pair of angle shifts: the counterclockwise angle between $\psi_1$ and $\psi_3$ , between $\psi_2$ and $\psi_4$ , and so forth. Since the average single angle shift is $2\pi/n$ , the average of these double shifts is $4\pi/n$ . Since $n\ge 4$ , one of these double angle shifts between $\psi_{i-1}$ and $\psi_{i+1}$ must be at least $\pi$ . That means that $\psi_{i+1}$ is counterclockwise from $\psi_{i-1}$ ! Therefore we can simply skip $\psi_i$ , leaving us with a shorter cycle $\psi_1\sim\ldots \psi_{i-1}\sim\psi_{i+1}\sim\ldots \psi_n\sim\psi_1$ . This is illustrated in the example below, where the red edges can be replaced by the dotted edges.

a decomposition of the previous 4 points on a circle into 2 directed triangles

Since any cycle of length greater than 3 can be shortened, we can continue shortening a cycle until we find its subcycle of length 3. That shows the first property.

Second Claim: conditions when no cycle exists

We want to show that there is no cycle if and only if there exists an angle which every other angle beats, so consider the example below. Since every angle beats $\psi_4$ , $\psi_4$ beats nothing, and there is no cycle.

4 different points on a circle where one angle beats all the others

If there is an angle $\psi_i$ which every other angle beats, then that $\psi_i$ doesn't beat anything. Then the entire swath of circle between angles $\psi_i$ and $\psi_i + \pi$ must be empty. Since an angle can only beat angles that are within $\pi$ of it in the counterclockwise direction, no sequence of $\psi$ 's can get past this swath, so there can be no cycle.

And if there is a cycle, then every angle on the cycle beats at least one other angle and is beaten by at least one other angle. Any angle not on the cycle must be between two points on the cycle, so must be less than $\pi$ radians clockwise from one and less than $\pi$ radians counterclockwise from the other. Therefore if a cycle exists, every angle has at least one edge going into it and one coming out. That shows the second property.

Interpolation!

If you know the temperature at various weather stations around the globe and want to estimate it a some point $p$ , you will need to pick 3 surrounding weather stations to interpolate between. A human could (with a bit of difficulty) find a set of weather stations which encompass $p$ (or decide there is no such set), but how would you rigorously explain how you found those stations?

There are a few ways to program the solution. The first is Delaunay triangulation, in which we draw a bunch of non-intersecting lines between these weather stations so that the whole sphere is covered in spherical triangles. Then we simply choose the weather stations forming the vertices of the triangle surrounding our point. The advantage to this approach is that it gives you a consistent approximation every time you estimate the temperature at a new point on the globe. The disadvantage is that using Delaunay triangulation and determining which spherical triangle $p$ lies in are difficult programming challenges.

Another approach is to look directly at the point in question, then try to find a triangle surrounding it. Each weather station must be at some angle relative to this point, so the problem of finding such a triangle reduces to the problem of finding a cycle in one of the tournaments described above. We can determine whether $\psi_i$ and $\psi_j$ go in counterclockwise order by whether the determinant of $(x_i, p, x_j)$ is negative, where $x_i, x_j$ are the coordinates of weather stations $i$ and $j$ . Using this for every pair of weather stations gives us a tournament, and our problem is to find a cycle in this tournament. Using the properties above, we can quickly deduce whether such a cycle exists, and some basic algorithms let us find a good cycle pretty quickly.

I implemented this second approach, taking temperature data from various cities on the globe today. I learned a bunch of capitals in the process.

< previous next >