Weak visibility and related problems on simple polygons

Abstract

Visibility and shortest path problems are two important areas of research in computational geometry. In this thesis we study weak visibility and related problems on simple polygons and propose efficient algorithms. We study convexity properties of shortest paths between arbitrary pairs of vertices and demonstrate their use in the design of efficient algorithms. We characterize weak visibility polygons in terms of a new convexity property of shortest paths between arbitrary pairs of vertices. Based on the characterization we propose (i) linear time algorithms for computing the shortest path tree rooted at any vertex of a weak visibility polygon, (ii) an algorithm for recognizing weak visibility polygons whose running time is proportional to the size of the visibility graph of the input polygon, and (iii) an algorithm for computing the maximum hidden set in a polygon weakly visible from a convex edge. We characterize the class of palm polygons in terms of the shortest path between arbitrary pairs of vertices. We use this characterization to design an algorithm for recognizing a palm polygon and computing the palm kernel. The algorithm runs in time proportional to the size of the visibility graph of the input polygon. Our algorithms use simple data structures.