Recognizing s-star polygons

摘要

We consider the problem of recognizing star-polygons under staircase visibility (s-visibility). We show that the s-visibilitypolygon 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 present an algorithm for computing the s-kernel of a polygon in O(n) time for simple orthogonal polygons and in O(n2) time for orthogonal polygons with holes; both complexities are optimal in the worst case. Finally, we report the main result of this paper: we show that even though the s-kernel of a polygon with holes may have Ω(n2) components it is possible to recognize such polygons in O(n log n) time.