Time-Space Trade-off Algorithms for Triangulating a Simple Polygon

An $s$-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses $O(s)$ additional words of space. We present a randomized $s$-workspace algorithm for triangulating a simple polygon $P$ of $n$ vertices that runs in $O(n^2/s+n \log n \log^{5} (n/s))$expectedtimeusing$O(s)$variables,forany$s \leq n$. In particular, when $s\le \frac{n}{\log n{\log }^5\log n}$ the algorithm runs in $O(n^2\mathrm{/}s)$ expected time.