Home » maths » graph theory » Testing a Manifold for Orientability

# Testing a Manifold for Orientability

Today it is time to reap the rewards of our efforts in turning a graph of a triangulated manifold into a triangulation data structure.  Using this data structure we will be able to determine if a manifold is orientable with ease.

Orientation

Orientation is a rather subtle concept, but it is an extremely important feature of space, underlying much of calculus. In $\mathbb{R}^n$, an orientation is a choice of an ordered basis $e_1, \dots ,e_n$, or rather a choice of representative of an equivalence class of ordered bases, where one basis $e_1, \dots, e_n$ is equivalent to another $e_1^*, \dots , e^*_n$ when the determinants of the two matrices formed by taking the basis elements to be columns, have the same sign.

In $\mathbb{R}^2$ then the order of your basis, consisting of two independent vectors, will either be clockwise or anti(counter)clockwise.

Recall that a 2-manifold is a space where every point is surrounded by a patch that looks like $\mathbb{R}^2$, and so the natural thing to do to orientate a 2 manifold, is to choose, for each patch, which way is clockwise. The problem with doing this is that small loop, or a ticking clock-face,moved around the manifold might start at a patch telling the clock it is ticking clockwise – as all clocks love to do – but then as it gets moved around it might land on a patch telling the clock it is going counterclockwise – a scandal! The thing that makes it difficult to avoid such a disaster, is that we insist that the local orientations behave ‘nicely’ where they overlap.

For a smooth manifold, that is one where the concept of ‘looks like’ is an infinitely differentiable homeomorphism, this simply means that if  patch $P_1$ in the manifold looks like $O_1$ in $\mathbb{R}^2$ and $P_2$ looks like $O_2$, then on the overlap $P_1 \cap P_2$ of the patches, there is an induced ‘transition’ function $f$ between a bit of between $O_1$ and $O_2$. So we want this induced function to be orientation preserving, meaning that the determinant of its Jacobian (the matrix of partial derivatives) is positive.

To see how this can go wrong, consider the Mobius Strip. An ant crawling on its surface thinks that its side is ‘up’, and this determines a notion of clockwise for the ant, but somehow after doing one lap of the strip, it has ended up of the other ‘side’ of the strip, and so at its starting point the poor ant is confused, which direction is really clockwise? To visualise this you should watch this clip I have found on youtube.

For manifolds that are not smooth it is a bit more complicated, but the picture of a shape getting reflected is still valid.

Orientating a Triangulated Manifold

Given a triangulation of a manifold, we can orientate each triangle by choosing an ordering of its vertices. In this case, the requirement that the overlaps be nice means that adjacent triangles should disagree about the ordering of their shared vertices. That is, if the shared edge has vertices A, B, then one triangle should say B comes before A, and the other one should say that A comes before B.

The way I like to think about this is again with a clock, start your clock off in some triangle, the ordering of the vertices is either in the same direction as the ticking of the clock, or the opposite. If the ordering of the vertices is in the same direction as the ticking of the clock, the triangle calls the clock clockwise, and everything is cool. Now let’s have a diagram to see why the neighboring triangle should invert the ordering of the shared nodes:

Observe that flipping the order of the shared nodes preserves the orientation.

So in order to show a manifold is orientable, for which we have a triangulation, we just need to produce such an ordering of the nodes. Conversely if we cannot find such an ordering, then the manifold must be non-orientable like the Mobius Strip. In order to prove this statement we would need a more precise discussion of a manifolds, but I think that it is intuitively clear (for the case of 2-manifolds at least).

The Code

We will again use a depth first search idea, we start at any triangle and choose an orientation. An orientation means a choice of which vertex comes next for any vertex. Once we’ve done that we look at each ordered edge of the triangle, then we go to its neighbor sharing that edge, and tell it to choose the orientation where the vertices are the other way around. If we’ve seen it before, we check that the choice of orientation agrees, if not, the manifold is not orientable. Simple!

So we add an is_orientable method to the Triangulation class.

class Triangulation(tig.UnDirGraph, object):
def __init__(self, **kwargs):
super(Triangulation, self).__init__(Vertex=Triangle_Node,**kwargs)

def is_orientable(self):
for triangle in self.vertices:
triangle.seen_before=False #Marks as unseen for the depth first search.

def orientable_search(triangle, A,B): # Check if A comes before B, or set it so that it does.
if triangle=='Boundary': #This is the case where a triangle's neighbor is the boundary.
return True
elif triangle.seen_before: #Checks if orientations consistent.
if triangle.orientation[A]==B:
return True
else:
return False
else:
triangle.seen_before=True
triangle.set_orientation(A,B)
#Now we go to each neighbor and flip the orientation, so B before A.
b_x=orientable_search(triangle.neighbors[(A,B)], B,A)
C=triangle.orientation[B]
b_y=orientable_search(triangle.neighbors[(B,C)], C,B)
b_z=orientable_search(triangle.neighbors[(C,A)], A,C)
return (b_x and b_y) and b_z #Makes sure they are all true.
#Now we initiate the orientation with an arbitrary first choice.
first_triangle = self.vertices[0]
return orientable_search(first_triangle, first_triangle.A, first_triangle.B)

Great! Now let’s do a quick sanity check and triangulate the sphere. The sphere is a 2-manifold of course, and a triangulation of it could be the tetrahedron, or the complete graph on 4 vertices, which we can generate easily. Interestingly, the graph of triangles of the tetrahedron is just the tetrahedron again! This is because it is self-dual.

graph=tig.Complete(4)
G=triangulate(graph)
print G.is_orientable()
for v in G.vertices:
o=v.orientation
label=str([v.A, o[v.A], o[o[v.A]]])
v.label=label
G.plot()

So the is_orientable method says the sphere is orientable, hurray!

But in case we didn’t trust it, I also labeled each triangle with the ordering of the vertices, and so now when we plot it, we can check that for each pair of nodes, the numbers (indexes of vertices in the original tetrahedron), they share in common from their shared edge, fall in the opposite order. It looks like this:
And that is that! Next time we will see that we can use this to automagically classify any  triangulated compact manifold without boundary.