Master of Science in Computer Science
First Committee Member
Second Committee Member
Third Committee Member
Fourth Committee Member
Number of Pages
We review important algorithmic results for the coverage of 1.5D terrain by point guards. Finding the minimum number of point guards for covering 1.5D terrain is known to be NP-hard. We propose two approximation algorithms for covering 1.5D terrain by a fewer number of point guards. The first algorithm (Greedy Ranking Algorithm) is based on ranking vertices in term of number of visible edges from them. The second algorithm (Greedy Forward Marching Algorithm) works in greedy manner by scanning the terrain from left to right. Both algorithms are implemented in Python 2.7 programming language.
Approximation; Greedy forward; Greedy ranking; Illumination; Terrain; Visibility
Khatiwada, Jiwan, "Approximation Algorithms for Illuminating 1.5D Terrain" (2019). UNLV Theses, Dissertations, Professional Papers, and Capstones. 3629.