Dean, J. A., Lingas, A., and Sack, J.-R. (1986). On Recognizing Polygons, or how to Eavesdrop. Technical Report LiTH-IDA-R-86-41, Department of Computer and Information Science, Linköping University, Sweden. Also in Proc of the Allerton Conference on Communication, Control, and Computing, Urbana, Illinois, 1986. (bibtex),
Abstract: A new class of so called pseudo star-shaped polygons is introduced. A polygon is pseudo star-shaped if there is a point from which we can see/eavesdrop its whole interior provided that it is possible to see/hear through its single edges. The class of pseudo star-shaped polygons generalizes and unifies the well known classes of convex, monotone and pseudo 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. Also, we show that many standard computational geometry problems can be solved efficiently for pseudo star-shaped polygons.
CS Dept TR Overview