From Algorithm Wiki
Revision as of 18:23, 11 September 2014 by Algowikiadmin
The algorithm Which I am presenting requires a HUGE amount of memory.. but gives O(n).. for "n" triangles
Consider the representation of data, the same way as in the war story. i.e a number vertices, and Triangles mentioned as a set of 3 vertices. We will keep one adjacency Matrix. This matrix will tell whether or not an edge exists. If an edge exists, the matrix contains the pointer to the element representing the edge. Initially the Matrix is empty and have no idea about the edges. We will maintain an array of edges. Every element of this array will basically point to a list of triangles, that contain that edge. (This is similar to an adjacency list, where every vertex maintains a list of adjacent vertices). For example: e1 -> T4 (Edge 1 is contained in Triangle 4) e2 -> T3 (Edge 2 is contained in Triangle 3).. Now when we read a triangle, for every edge we check if that edge element is present in the Matrix. If so, the Matrix contains the pointer to the edge element. This edge element can be present in only 1 other Triangle. So we immediately get The triangle sharing the edge. This way we can get all adjacent Triangles (Max 3, one for each edge) for every triangle in constant time. For n triangles, this gives O(n) running time.