Given a list of diagonals of a polygon forming a triangulation, design an algorithm to build the dual tree

2018-10-04 15:24:36

A triangulation $T$ of $P$ is a maximal crossing-free geometric (i.e., straight-line) graph whose vertices are the vertices of $P$ and whose edges lie inside $P$.

The dual graph of a triangulation $T$ is the graph with a vertex for each bounded face of $T$ and an edge between two vertices if and only if the corresponding triangles share an edge in $T$.

The question below is taken from "Computational Geometry in C" by Rourke.

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 using $O(n)$

time and $O(n^2)$ space.

I have no idea on how to design this algorithm. So, even a good idea would be appreciated.