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 visibility graph (PVG) of P. In this paper we explore the use of perfect graphs to characterize tractable subproblems of visibility problems. Our main result is a characterization of which polygons are guaranteed to have weakly triangulated PVGs, under a generalized notion of visibility called O-visibility. 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 such that a "reflex" local maximum in the boundary of P exists with respect to theta. Our characterization of which polygons have weakly-triangulated PVGs is based on restricting the cardinality and span of O'. This characterization allows us to exhibit a class of polygons admitting a polynomial algorithm for O-convex cover.
convex cover approximation restricted orientation generalized visibility