Applications of visibility space in polygon search problems

This thesis investigates several problems related to searching a polygonal area for intruders. The mutual visibility between an arbitrary pair of points on the boundary of a polygon is an important piece of information we can make use of when searching a polygon. We extensively employ the visibility diagram that represents mutual visibility information for each pair of boundary points. We first investigate the two-guard room search problem, where two guards cooperate in finding an intruder by maintaining mutual visibility. In terms of the visibility diagram we characterize the class of searchable rooms in a concise way. We also find all doors in a polygon, if any, such that the resultant rooms are searchable by two guards. The second problem we tackle in this thesis is the polygon search problem by a boundary 1-searcher, who moves along the boundary of a polygon and can see the points on the beam from a flashlight. We identify the patterns that make a polygon non-searchable. The third problem we investigate is to search a polygon with one hole by two boundary 1-searchers. We solve this problem by extending the visibility diagram.