A recent video by 3Blue1Brown (previously seen generating Pi from bouncing blocks) introduced me to an interesting problem from the 2011 International Mathematical Olympiad. The problem (described below) describes a windmill process where a line rotates through a cloud of points, switching pivots whenever it hits a new point.

I found the video really informative and the process mesmerizing to watch, so I just had to code up a simulation of the process to play with. The end result can be seen below. In the rest of this post, I will talk about the problem and how I implemented it.

Larger version

In this demo, you can generate a point cloud and watch the windmill rotate. You can switch the pivot by clicking on a point. You can also ask the demo to “solve” the problem.

The problem

For our problem, we examine a windmill process. We start with a set of points on a plane S\mathcal{S} and a pivot point P∈S\mathcal{P} \in \mathcal{S}. No three points in S\mathcal{S} are collinear meaning that no three points are on the same line. We then draw a line ℓ\ell through P\mathcal{P} and start rotating the line clockwise.

Whenever the line hits another point in S\mathcal{S}, that point becomes our new pivot, and we continue rotating the line. The non-collinearity property ensures that we will never hit two new points at the same time. Our question then is: can you pick a starting pivot P\mathcal{P} so that every point will be hit infinitely many times?

Before we look at the actual solution, I’d like to mention a few insights. Given that we want to hit every point infinitely many times, we want to find a cycle that hits every point at least once. We can also look at the opposite problem. Can we pick a starting pivot so that we don’t hit every point infinitely many times, i.e. can we find a cycle that never touches some points?

The answer to that last question is a yes, at least sometimes. If the points in S\mathcal{S} do not form a convex hull, we can start with our line perfectly vertical at the leftmost point of the convex hull of S\mathcal{S} and the line will simply walk the the convex hull, skipping any interior points.

The solution

If you play with the demo, you may notice that the line will circle around the center of the point cloud. If the line starts in the center of the cloud, it will stay in the center, and if it starts at the edge, it will stay at the edge. Obviously, if we stay in the center, we will hit every point in a full rotation. Now let’s prove this.

After selecting an initial pivot, the number of points on either side of the line stays the same. When a we hit a new pivot, we have two options:

  • The new pivot is above the current pivot. This means that it was originally on the right of the line since the line had to rotate into it. When the line rotates on, this means that our original pivot is now on the right of the line, maintaining the status-quo.
  • When the new pivot is below our current pivot, the situation is the opposite. The new pivot must have been on the left, and our old pivot will end up on the left.

We can use this invariant to choose or pivot so that yes all points are hit at least once. To do so, we just need to have as many points on the left as on the right, and the line pointing straight up.

When we our line has made half a rotation, we still have the same number of points on the left as on the right, although left and right has changed. If we had an odd number of points, this must mean that our current pivot is the same as the one we started with, since there is only one point with as many points to its left as to its right. Since the only way to switch sides of the line is to get hit by the line, this must mean that we hit every point at least once.

If we started with an even number, things are more complicated since we lose our symmetry, but luckily it doesn’t get that much more complicated. If the number of points ∣S∣=N|\mathcal{S}| = N, we pick the n=N2n = \frac{N}{2}th point from the left, so that we have nn points on the left and n−1n - 1 on the right of the pivot.

Now, if we rotate half a circle, every point has flipped sides, except for two: our initial P\mathcal{P} which is now on the right side of the line, and the point directly next to it, which has become the current pivot. If we once again turn half a circle, this flips again, and we are back in our starting position.

This explanation is based on the explanation by 3Blue1Brown in his video starting from about 9 minutes in. Please do watch his video; he explains it better and with nicer graphics than I do or can.

The demo

Now to actually make this work. There are roughly two parts to this: showing it visually and actually simulating the problem. For my visualisation, I chose to use SVG because it allows me to easily scale the resulting images, and saved me from wrapping my head around coordinates. I can simply add circle elements and specify coordinates, optionally adding a pivot-class when relevant. Drawing a line is not much harder, except that SVG doesn’t do infinite lines. Instead, I just use a line that over-scans the view box by a lot. So with that out of the way, I will go over the algorithmic details of implementing the demo.

Initialization

In order to generate our point cloud we simply generate 2×n2 \times n random numbers between zero and one and be done. This does not guarantee that no 3 of those points are on one line. We can technically just check new candidates and discard them when they are invalid, but:

  • checking the iith requires evaluating all (i−1)(i−2)(i - 1)(i - 2) existing pairs causes the point generation process to be O(n3)O\left(n^3\right) which gets expensive at higher point counts,
  • checking is not even necessarily feasible due to floating point rounding errors in JavaScript, but all of that doesn’t matter because
  • the probability of completely random points being multicollinear is very near zero since R\mathbb{R} is just really large.

I really wanted to find a source that proces the last one, it just intuitively feels true, but I didn’t. If you have one please get in touch.

Finding collisions

If we want to rotate our line around like the described windmill, we need to know when we are going to hit the next point. To do this, we can simply compute the angle between each point Qi\mathcal{Q}_i and the xx-axis relative to our current pivot P\mathcal{P}. We can then compare this to the current angle of our line, and determine which will bit hit first. Since we are only interested in hitting things with a clockwise rotation, we add half a circle if our result would be a counter-clockwise rotation. This works as follows:

Δi=Qi−P∠i=arctan⁡ΔiyΔix−∠ℓdistancei={∠iif ∠i≥0∠i+πotherwise\begin{align*} \Delta_{i} &= \mathcal{Q}_{i} - \mathcal{P} \\ \angle_{i} &= \arctan{\frac{\Delta_{iy}}{\Delta_{ix}}} - \angle_{\ell} \\ \mathit{distance}_i &= \begin{cases} \angle_{i} & \text{if $\angle_{i} \geq 0$} \\ \angle_{i} + \pi & \text{otherwise} \end{cases} \end{align*}

All that remains is doing this for every point, finding the one with the smallest distance to hit, rotating by a bit, and continuing on. There is one slight caveat: when you are currently hitting two points, you will start flip-flopping between them when trying to compute the next point to hit. There are various ways you can work this, but I decided that I would ignore all points with a rotation less than some ϵ\epsilon, in this case 10−610^{-6}. As far as I know, this doesn’t cause issues.

Final thoughts

I find the windmill problem discussed in this post rather beautiful. Its statement is very easy to understand and visualize, and its solution and proof can be understood by everyone. Crafting the visualisation for it really made me appreciate it even more.

On the other hand, creating that visualisation with SVG was a nice experience getting a bit deeper into that. Sure, you can draw al this on a <canvas> element but why would you? SVG gives you all sorts all sorts of viewbox control without having to work for it, and you can even depend on CSS to do your styling. All around a nice exercise.