AN OVERVIEW OF VISIBILITY PROBLEM ALGORITHMS IN 1,5D

B. Kaucic

B. Zalik

Department of mathematics, Faculty of Education
Koroska c. 160, SI-2000 Maribor,

Faculty of Electrical Engineering and Computer Science
Smetanova 17, SI-2000 Maribor

Slovenia
{branko.kaucic|zalik}@uni-mb.si}

Abstract

The paper gives an overview of algorithms for the terrain visibility problem. First, a comprehensive background of the problem is given. It is explained how the 2,5D problem is transformed to a 1,5D problem. Next, six algorithms (a naive approach, an approach with the height of line-of-sight (LOS), an approach with the biggest slope of LOS, an approach with the cross product, an incremental approach, and an improved incremental approach) are briefly explained and their theoretical time complexities are given. After that, run-times of the algorithms are measured for different terrain configurations and different viewpoint heights. The best algorithm is selected at the end.