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!