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:

oriented_triangles

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:
triangulated_sphereAnd that is that! Next time we will see that we can use this to automagically classify any  triangulated compact manifold without boundary.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: