In this paper the authors consider some visibility problems for polyhedral terrains (polyhedral surfaces that have exactly one intersection with each vertical line); these problems are three-dimensional generalizations of planar visibility problems. They develop efficient preprocessing techniques for the case in which the viewpoint is fixed and lies above the terrain and for the case in which the viewpoint varies along some fixed vertical line. If the line is not vertical the complexity of the visibility structure increases.

In the last part of the paper, the authors consider the problem of placing one or several viewing points on the polyhedral surface so that they collectively cover the entire surface. If only one point is needed, the authors present an algorithm to locate it, which runs in time O(n log n), where n is the number of faces. They prove that the problem of finding the smallest number of points on a surface that can collectively see the entire surface is NP-hard. Finally, they formulate some open problems.

Knowledge of topics like data structures, computational geometry, and computational complexity of the calculus facilitates the understanding of the text. A complete analysis of the computational complexity of these problems, a suitable length, and new references are important features of the paper. This approach is efficient, and the authors’ results are important for many applications in computer graphics and image processing.