Fast Heuristics for Covering 1.5D Terrain
Document Type
Conference Proceeding
Publication Date
5-12-2020
Publication Title
17th International Conference on Information Technology–New Generations (ITNG 2020)
Publisher
Springer
Publisher Location
Las Vegas, NV
First page number:
571
Last page number:
577
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 an approximation algorithm for covering 1.5D terrain by a few number of point guards. The algorithm which we call Greedy Ranking Algorithm is based on ranking vertices in term of number of visible edges from them. We also present an improvement of the Greedy Ranking Algorithm by making use of visibility graph of the input terrain.
Keywords
Terrain visibility; Tower placement algorithm; Terrain illumination
Disciplines
Computer Sciences
Language
English
Repository Citation
Gewali, L.,
Khatiwada, J.
(2020).
Fast Heuristics for Covering 1.5D Terrain.
17th International Conference on Information Technology–New Generations (ITNG 2020)
571-577.
Las Vegas, NV: Springer.
http://dx.doi.org/10.1007/978-3-030-43020-7_75