# 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 is possible. – Evil Nov 28 '17 at 11:29

Yes, "it's easy to derive from such a decomposition of $P$ in linear time a triangulation of $P$."