Computational problems in strong visibility

Eugene Fink and Derick Wood

In Proceedings of the Vision Geometry VI Conference, pages 95-105, 1997.

Abstract

Strong visibility is a generalization of standard visibility, defined with respect to a fixed set of line orientations. We investigate computational properties of this generalized visibility, as well as the related notion of strong convexity. In particular, we describe algorithms for the following tasks:

• Testing the strong visibility of two points in a polygon and the strong convexity of a polygon.
• Finding the strong convex hull of a point set and that of a simple polygon.
• Constructing the strong kernel of a polygon.
• Identifying the set of points that are strongly visible from a given point.