Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon
Danny Z. Chen · Journal of Algorithms · 1996
Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n2) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear.