Award Date

May 2018

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Laxmi Gewali

Second Committee Member

John Minor

Third Committee Member

Kazem Taghva

Fourth Committee Member

Henry Selvaraj

Number of Pages

48

Abstract

We review existing algorithms for the placement of towers for illuminating 1.5D and 2.5D terrains. Finding the minimum number of towers of zero height to illuminate 1.5D terrain is known to be NP-Hard. We present approximation algorithms for solving two variations of the tower placement problem. In the first variation, we consider the placement of a single tower of given height to maximize visibility coverage. In the second variation, we consider the problem of placing reduced number of common height towers to cover the entire terrain. Algorithms for solving both problem variations are based on discretizing the problem domain by carefully identifying feasible placement points. We also present a Java implementation for placing a single tower of minimum height to illuminate a given 1.5D terrain.

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