Testing a simple polygon for monotonicity optimally in parallel (Q688449)

We show that an \(n\)-vertex simple polygon can be tested in parallel for monotonicity optimally in \(O(\log n)\) time using \(n/\log n\) EREW PRAM processors, and we present two different optimal parallel algorithms for solving this problem. Our results leads to an optimal parallel algorithm for triangulating simple polygons that runs in \(O(\log n)\) time using \(n/\log n\) EREW PRAM processors if the polygons are monotone.