Polygon visibility decompositions with applications.

Abstract

Many problems in Computational Geometry involve a simple polygon P and a family of geometric objects, say sigma, contained in P. For example, if sigma is the family of chords of P then we may want to find the longest chord in P. Alternatively, given a chord of P, we may wish to determine the areas of the two subpolygons of P determined by the chord. Let pi be a polygonal decomposition of a polygon P. We call pi a visibility decomposition with respect to sigma if, for any object g ∈ sigma, we can cover g with o(|P|) of the subpolygons of pi. We investigate the application of visibility decompositions of polygons to solving problems of the forms described. Any visibility decomposition pi of a polygon P that we construct will have the property that, for some class of polygons ℘ where the polygons in ℘ have useful properties, pi ⊆ ℘. Furthermore, the properties of ℘ will be key to solving any problems we solve on P using pi. Some of the visibility decomposition classes we investigate are already known in the literature, for example weakly edge visible polygon decompositions. We make improvements relating to these decomposition classes and in some cases we also find new applications for them. We also develop several new polygon visibility decomposition classes. We then use these decomposition classes to solve a number of problems on polygons including the circular ray shooting problem and the largest axis-aligned rectangle problem. It is noteworthy that the solutions to problems that we provide are usually more efficient and always simpler than alternative solutions.