Computing Visibility Properties of Polygons

In many pattern recognition problems the objects of interest are represented as polygons. For some applications such as pattern matching the shape of the polygons is successfully measured in terms of the visibility relations between the edges. In this paper we survey some recent results in computational geometry that allow efficient computation of visibility properties between edges of a simple polygon as well as more general visibility relations. In particular, four natural definitions of edge-to-edge visibility are considered and a linear-time, and thus optimal, algorithm is discussed to determine edge-to-edge visibility under any of the four definitions. Furthermore, an O(n log log n) time algorithm is reviewed for determining that region of an n-gon P that is weakly visible from a specified edge of P (the strong hidden-line problem). The algorithm combines results from visibility and geodesic paths with the recent polygon triangulation algorithm of Tarjan and Van Wyk [42]. We also discuss the problem of determining whether a polygon is visible from a specified edge. In particular three natural definitions of edge-visibility of polygons are considered and new optimal algorithms are proposed for testing visibility from a specified edge under any of the three definitions.