An optimal parallel algorithm for detecting weak visibility of a simple polygon
Danny Z. Chen · 1992
The problem of detecting the weak visibility of an n-vertex simple polygon P is that of finding whether or not P is weakly visible from one of its edges and (if it is) identifying every edge from which P is weakly visible. In this paper, we present an optimal parallel algorithm for solving this problem. Our algorithm runs in O(log n) time using O(n/log n) processors in the CREW-PRAM computational model, and is very different from the sequential algorithms for this problem. This algorithm also enables us to optimally solve, in parallel, several other problems on weakly visible polygons.