Algorithm design - a better way of finding sets of triangles that share a vertex

Question

I'm trying to calculate a Voronoi graph from a Delaunay Triangulation, I've got the triangulation data in the form of a collection of verticies (red circles on graph) and triangles (blue lines on graph):

I'm able to calculate the Voronoi graph verticies easily (the intersection of the red lines) by just getting the circumcenter of all the triangles.

However, I need to derive the 'cell' information for each red polygon. To do this, for each red vertices I need to find a set of triangles that share that same vertex. So for the circled vertex, I need the green triangles:

So my code looks like this (c#):

    foreach (Vertex3 vertex in DelaunayVertices)
    {
        VoronoiCell cell = new VoronoiCell();
        cell.Vertex = vertex;

        //seach all triangles for the ones that match this.
        foreach (Face3 face in DelaunayTriangles)
        {
            if (face.Vertices.Where(v => v.Equals(vertex)).Any())
            {
                //shares vertices, add it's circumcenter as an edge vertex of the cell
                cell.EdgeVertices.Add(face.Circumcenter);
            }
        }
    }

Which is of course, hugely inefficient, as it's searching everything. However, the collections of faces, or verities are completely unsorted (and I'm unsure exactly how to sort them, or if it would help). Just to be confusing, there are 3 dimensional vertex on the surface of a sphere.

The only thing I have to find adjacent vertexes or faces for each triangle I have it's Adjacency, so for the orange triangle below, I know the three green triangles:

I'm thinking it might be more efficient to traverse this graph, but I'm struggling to come up with an approach to an algorithm that will produce sets that share points.

Answer 1

If you're willing to store a secondary vertex-to-triangle data-structure, you can first traverse the triangle list, pushing each triangle onto the adjacency lists associated with its three vertices:

for (all tria's ti)
    for (all nodes ni in tria ti)
        v2t[ni] <- ti
    end for
end for

This is just an O(n) sweep.