Award Date

5-1-2019

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Laxmi Gewali

Second Committee Member

Kazem Taghva

Third Committee Member

John Minor

Fourth Committee Member

Henry Selvaraj

Number of Pages

53

Abstract

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.

Keywords

Approximation; Greedy forward; Greedy ranking; Illumination; Terrain; Visibility

Disciplines

Computer Sciences

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


Share

COinS