AbstractA chord of a simple polygon P is weakly-visible, if every point on P is visible from some point on the chord. We give an optimal linear-time algorithm which computes all weakly-visible chords of a simple polygon P with n vertices. Previous algorithms for the problem run in O(n log n) time, and only compute a single weakly-visible chord, if one exists.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: computational geometry, visibility, polygons, chords
Selected references
- D. T. Lee and F. P. Preparata. An optimal algorithm for finding the kernel of a polygon. Journal of the ACM, 26(3):415-421, July 1979.