Visibility properties of polygons

摘要

In this thesis, we establish tight bounds on the maximum size of maximum hidden sets, minimum guard sets, and minimum partitions and covers of polygons, using link-visibility. These results unify and generalize the guard set results (and combinatorial method) of Chvatal and O'Rourke. Our method also provides tight bounds on independent and dominating sets in triangulation graphs, and almost-tight bounds on the size of hidden sets, guard sets, covers, and partitions of polygon exteriors. We also prove that, using link-visibility, the optimization problems of finding maximum hidden sets, minimum guard sets, or minimum covers are NP-hard. Link-visibility is an extended notion of visibility arising from robotics and motion planning problems. Hidden sets are sets of points in a polygon such that no two points of the set are visible, and guard sets are sets such that each point of the polygon is visible to some point in the guard set. Both maximum hidden set sizes and minimum guard set sizes can be used as polygon shape complexity measures.