Given a trapezoidal map of a simple polygon $P$, is it possible to compute the triangulation of $P$ in $\mathcal{O}(n)$ time?
1 Answer
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.