**
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.