This paper represents a fusion of algorithmic concepts pulled from the work of several prominent researchers in the field of geographic information systems (GIS): P.K. Agarwal, J.S. Vitter, G.S. Brodal, L. Toma, and V. Kreveld, to mention just a few. The main purpose of the work is the search for an efficient method of computing visibility between two points at different elevations, within a surrounding terrain, using external input/output (I/O) devices.
The need for an efficient method of computing visibility between two geographic points becomes self-evident every time one uses a Web page to look at maps relating to weather, global positioning system (GPS) directions, geography, or even oceanography. These capabilities would not be there if it were not for the ability to use high-resolution terrain data gathered from satellite imaging in an intelligent way.
In this engaging and well-written paper, Haverkort, Toma, and Zhuang present: problems involved in calculating three-dimensional visibility from data stored in two-dimensional space array values; solutions of previous researchers; the improved algorithms tested; and results of their tests. The paper will also be of interest to anyone who is looking for I/O-efficient algorithms that help perform calculations across spatial relationships.
It is known that different technological areas experience different technological growth rates. This is the case with the fields of external I/O memory drives and central processing unit (CPU) design. As CPU speeds continue to grow, the variance between the amount of data they can process in a given time becomes more disparate from the amount of data that can be transferred into them; this is called the CPU memory gap. The CPU memory gap poses a constant challenge for computer experts, as they try to find new ways to overcome the disjointed operational speeds of CPUs and memory systems.
In addition, efficient I/O algorithms should also be of interest to all those who want their spatially oriented programs to run more efficiently.
