Triangulating a simple polygon via its trapezoidal map Given a trapezoidal map of a simple polygon $P$, is it possible to compute the triangulation of $P$ in $\mathcal{O}(n)$ time?
Yes, "it's easy to derive from such a decomposition of $P$ in linear time a triangulation of $P$."

Take a look at lemma 1. here.