On realistic terrains (Q934023)

This paper is focused on the worst-case complexities of the visibility map and the shortest paths on realistic polyhedral terrains. The authors give a set of input assumptions which can reasonably present the values of the model parameters in terrains that arise in practice. The minimal value of the angle in any triangle, edge length ratio and low-density triangulation are taken into the consideration in these assumptions. The authors show that only the given assumptions together (not separately) can achieve a subquadratic upper bound on the complexity for the visibility map of a terrain for both parallel and perspective views. Furthermore, an additional assumption is introduced for distance structures, bisectors, shortest path maps and Voronoi diagrams on terrains and the upper and lower bounds on their complexities is proved. The fourth input assumption relates to the steepness of the terrain.