Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon
✍ Scribed by Danny Z. Chen
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 209 KB
- Volume
- 20
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
Given an n-vertex simple polygon P, the problem of computing the shortest weakly visible subedge of P is that of finding a shortest line segment s on the Ž . boundary of P such that P is weakly visible from s if s exists . 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 algo-Ž . rithms for solving this problem. Our sequential algorithm runs in O n time, and Ž . Ž . our parallel algorithm runs in O log n time using O nrlog n processors in the CREW PRAM computational model. Using the previously best known sequential Ž 2 . algorithms to solve this problem would take O n 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.