Energy consumption of large commercial buildings has become higher than before, and a major part of the energy is on their lighting systems. This thesis aims at reducing the energy consumption of a building's lighting system. Our solution is to minimize the total number of necessary light fixtures in a commercial building, and thus we formulate the Constrained Light Deployment Problem (CLDP). The CLDP problem is tightly related to the Art Gallery Problem (AGP), a classical problem in computational geometry that finds the minimum number of guards to monitor a polygon area. Unlike the traditional AGP, however, our problem poses a new challenge that the illuminance of any spot in the building must be higher than a required threshold. To address the new challenge, we first propose an algorithm based on polygon partition and iteratively remove redundant light fixtures to obtain a tighter upper bound on the necessary number of light fixtures. We further improve the algorithm with clustering and binary search to reduce the number of light fixtures. Our algorithm can return the locations of resulted light fixtures, which are not necessarily the vertices of the orthogonal polygon. Simulation results demonstrate that our algorithm is fast and effective. / Graduate

In this thesis, we design and develop new approximation algorithms and complexity results for three guarding and partitioning problems on orthogonal polygons; namely, guarding orthogonal polygons using sliding cameras, partitioning orthogonal polygons so as to minimize the stabbing number and guarding orthogonal terrains using vertex guards. We first study a variant of the well-known art gallery problem in which sliding cameras are used to guard the polygon. We consider two versions of this problem: the Minimum- Cardinality Sliding Cameras (MCSC) problem in which we want to guard P with the minimum number of sliding cameras, and the Minimum-Length Sliding Cameras (MLSC) problem in which the goal is to compute a set S of sliding cameras for guarding P so as to minimize the total length of trajectories along which the cameras in S travel. We answer questions posed by Katz and Morgenstern (2011) by presenting the following results: (i) the MLSC problem is polynomially tractable even for orthogonal polygons with holes, (ii) the MCSC problem is NP-complete when P is allowed to have holes, and (iii) an O(n)-time exact algorithm for the MCSC problem on monotone polygons. We then study a conforming variant of the problem of computing a partition of an orthogonal polygon P into rectangles whose stabbing number is minimum over all such partitions of P. The stabbing number of such a partition is the maximum number of rectangles intersected by any orthogonal line segment inside the polygon. In this thesis, we first give an O(n log n)-time algorithm that solves this problem exactly on histograms. We then show that the problem is NP-hard for orthogonal polygons with holes, providing the first hardness result for this problem. To complement the NP-hardness result, we give a 2-approximation algorithm for the problem on both polygons with and without holes. Finally, we study a variant of the terrain guarding problem on orthogonal terrains in which the objective is to guard the vertices of an orthogonal terrain with the minimum number of vertex guards. We give a linear-time algorithm for this problem under a directed visibility constraint. / February 2016