IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Fri, 18 Apr 2014 02:43:59

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.

Goto (at Linköping University): CS Dept TR Overview