Computing stair-case visibility polygon
Laxmi P. Gewali · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1993
Given a point q in the presence of polygonal obstacles, the set of points visible from q is the visibility polygon from q. We consider the problem of computing visibility polygon under stair-case visibility (s-visibility, in short). We show that the s-visibility polygon from a point inside a simple orthogonal polygon of n sides can be computed in O(n) time. When the polygon contains holes the algorithm runs in O(n log n) time, which we prove to be optimal by linear time reduction from sorting. We also consider the problem of recognizing stair-case star polygons (s-star, in short) and present an algorithm which recognizes simple s-star polygons in O(n) time.