TADM2E 5.11

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.

Another solution using a hash-table

This solution is similar to the above, but it uses an array of hashtables to maintain the mapping from seen edges to triangles. The key observation is that any edge in the triangulation can be seen at most twice. When we see the $ k^{th} $ triangle $ (x_{k1}, x_{k2}, x_{k3}) $, we take each edge $ (x_{ki}, x_{kj}) $ such that $ x_{ki} \lt x_{kj} $ (i.e., in the sorted order of vertex numbers in triangle $ k $), and do the following (H is the array of $ m $ hashtables, where $ m $ is the number of vertices in the triangulation. Note that this can easily also be made a hashtable of pointers to hashtables to save space)

• If the hashtable for $ x_{ki} $ ($ H[x_{ki}] $) doesn't exist yet, create and initialize it.
• Check if an item with key $ x_{kj} $ exists in $ H[x_{ki}] $.
  • If not, this is the first time we are seeing this edge $ (x_{ki}, x_{kj}) $, so add $ k $ under the key $ x_{kj} $ in $ H[x_{ki}] $ and continue.
  • If yes, retrieve the element (say with value $ l $), add an edge from $ k $ to $ l $ in the dual graph and (optionally) delete the item from $ H[x_{ki}] $.

We repeat the above for each of the three edges of each triangle in the triangulation. Since the operations above can be implemented to be run in (amortized) constant time, and we consider no more than $ 3n $, $ n $ being the number of triangles in the triangulation, the algorithm runs in $ O(n) $ time.