Technical challenges in computational geometry
27 Nov 2018 CloudNC

Computational geometry is a fascinating domain filled with technical challenges that often seem simple, but equally often turn out to be complicated. For example, suppose you’re given one direction and asked to choose two other directions such that all three are orthogonal (i.e., mutually perpendicular). An intuitive solution is obtained by holding your hand in the shape of the right-hand rule with your thumb pointing in the direction you’re given so the other directions are indicated by your first and middle fingers. You’ll notice that you can rotate your hand freely around your thumb to get many equally valid answers. There seems to be a lot of choice, but does this make the problem easier.. or harder? 🤔 The right-hand rule is featured on the new 200 Swiss Franc (~£156) bank note, an expensive way to remember it! Source: www.banknotenews.com

## Computing an orthonormal basis

(From here on we assume some vector algebra and programming knowledge).

If we represent directions as unit vectors, our problem amounts to computing an orthonormal basis. A straightforward solution can be derived using basic vector algebra. We’ll call our three directions uv and w. Given a unit vector u, we first pick an arbitrary vector, say e = (1, 0, 0) and compute the component of e in the direction perpendicular to u, this is known as the rejection vector and denoted in the figure as eᵣ. You may be more familiar with the concept of projection, denoted ep below, rejection is analogous but in the perpendicular direction. Next we normalise eᵣ to obtain the second vector v, and finally we find the last vector by computing a cross product w = u x v.

There are a few problems with this approach. First, note that when u = e the algorithm doesn’t work, and we’ll need to pick a different e. In fact, we can work around the problem with a simple conditional / `if` statement, but this raises a question — is a conditional / `if` statement really needed in this context? By interpreting the conditional as a function discontinuity a possible solution presents itself: the branch could be removed by finding a continuous function, v(u) that assigns a unit tangent vector to every point, u, on the surface of a unit sphere. Unfortunately, a classic result known as the Hairy Ball Theorem, proven by Dutch mathematician L. E. J. Brouwer in 1912, demonstrates this is impossible in three dimensions, in fact the theorem actually states this is impossible in all odd dimensions! In two dimensions, for example, it is possible to construct such a function, namely v(u) = (-ba) with u = (ab).