# Algorithm for Triangulation Dual Tree

I am looking for algorithm for the following problem.

Given a list of diagonals of a polygon forming a triangulation, with each diagonal specified by counterclockwise indices of the endpoints, design an algorithm to build the triangulation dual tree. In advanced variant design an algorithm to build the triangulation dual tree in $O(n)$ time and $O(n^2)$ space.

So far I have few thoughts how to approach the solution for the problem.

If we were given the list of triangles, the problem would be easier. Because in this case we were looking for triangles that share the same diagonals, and these triangles would form adjacent vertexes of a dual tree. Of course we can identify diagonals which share a common vertex and assume that triangles that formed from these diagonals represent vertexes of a dual tree.

Another problem is I don't understand the order in which diagonals are presented in the list. The order seems to be a crucial part of the algorithm.

If you have any thought how to approach the above problem, please, share it with us.

Thanks!

-

In a pre-processing phase we record the adjacency information of the vertices by parsing through the edge-list. We add also the boundary edges and store the vertex degrees. This can be clearly done in $O(n)$ time and $O(n^2)$. Use a 2d array (adjacency matrix) for the adjacency information and a double linked list for the vertices.
In a second step the vertices are sorted by degree using Counting Sort, which also takes $O(n)$ time.
We now perform ear clipping and build the dual tree on the fly. To find an ear we look in the sorted degree vector for a degree 2 vertex. Then we delete this vertex and update the degree and adjacency information. Since we have only $O(n)$ edges and total vertex degrees the updates need only linear time in total. For all "intermediate" polygons we store a sub-tree for every boundary edge. If the two edges of an ear are removed, their trees $T_1$ and $T_2$ will be joined by adding a new vertex $r$ as root and making the roots of $T_1,T_2$ its children. The new tree will be associated with the diagonal that becomes a boundary edge after the clipping.