Point visibility graphs and O-convex cover

A visibility relation can be viewed as a graph: the uncountable graph of a visibility relationship between points in a polygon P is called the point v isibility graph (PVG) of P. In this paper we explore the use of perfect gra phs to characterize tractable subproblems of visibility problems. Our main result is a characterization of which polygons are guaranteed to have weakl y triangulated PVGs, under a generalized notion of visibility called O-visi bility. Let O denote a set of line orientations. A connected point set P is called O-convex if the intersection of P with any line with orientation in O is connected. Two points in a polygon are said to be O-visible if there is an O-convex path between them inside the polygon. Let O-perpendicular to denote the set of orientations perpendicular to orientations in O. Let O' subset of or equal to O-perpendicular to be the set of orientations theta s uch that a "reflex" local maximum in the boundary of P exists with respect to theta. Our characterization of which polygons have weakly-triangulated P VGs is based on restricting the cardinality and span of O'. This characteri zation allows us to exhibit a class of polygons admitting a polynomial algo rithm for O-convex cover.