Algorithms for minimum length sliding camera problem

Abstract

Art gallery problem is a well known visibility problem where objective is to cover the whole gallery by the minimum number of cameras. In computa- tional geometry galleries are represented by two dimensional polygons. There are many variants of the art gallery problem. One such variant is the minimum length sliding camera (MLSC) problem which uses sliding cameras that travel along the boundary of the polygon and cover orthogonally inside it. Here the objective is to cover the whole polygon by traversing the minimum length in the polygon’s boundary. There is an algorithm which solves MLSC problem in O(n2 ) time for orthogonal polygons. In this thesis we show that for some subclasses of orthogonal polygons one major step of that algorithm shows lower time complexity. So far, all the results of the art gallery problem with sliding cameras are for orthogonal polygons. But in reality some non-orthogonal edges may be incorporated in the polygon. Based on this requirement we develop an algorithm that solves MLSC problem for some subclasses of semi-orthogonal polygons in O(n2 ) time. The class of semi-orthogonal polygons is a superclass of orthogonal polygons. As a byproduct of our work, we establish some relations among different components of an orthogonal polygon after it is being rectan- gulated. Advancement in the wireless technology introduces new variants in the art gallery problem. One such variant is MLSCk problem. We consider few modifications in the MLSCk problem and termed it as modified MLSCk prob- lem. Here sliding k-transmitters are used which have infinite broadcast range, can penetrate at most k number of walls (k is an integer and k > 0), travel along the boundaries of an orthogonal polygon and can cover orthogonally inside the polygon. The objective is to find the minimum-length sliding k-transmitters that cover the entire orthogonal polygon. We develop an algorithm which finds the minimum length cover in O(n2 ) time.