Recognizing polygons, or how to spy (Q1104085)

A new class of so-called pseudo-star-shaped polygons is introduced. A polygon is pseudo-star-shaped if there exists a point from which the whole interior of the polygon can be seen, provided it is possible to see through single edges. We show that the class of pseudo-star-shaped polygons unifies and generalizes the well known classes of convex, monotone and star-shaped polygons. We give algorithms for testing whether a polygon is pseudo-star-shaped from a given point in linear time, and for constructing all regions from which the polygon is pseudo-star-shaped in quadratic time. We show the latter algorithm to be worst-case optimal. Also, we give efficient algorithms solving standard geometrical problems such as point-location and triangulation for pseudo-star-shaped polygons.