Herman Haverkort
Abstract
Given an arbitrary viewpoint v and a terrain, the visibility map or viewshed of v is the set of points in the terrain that are visible from v. In this article we consider the problem of computing the viewshed of a point on a very large grid terrain in external memory. We describe algorithms for this problem in the cache-aware and cache-oblivious models, together with an implementation and an experimental evaluation. Our algorithms are a novel application of the distribution sweeping technique and use O(sort(n)) I/Os, where sort(n) is the complexity of sorting n items of data in the I/O-model. The experimental results demonstrate that our algorithm scales up and performs significantly better than the traditional internal-memory plane sweep algorithm and can compute visibility for terrains of 1.1 billion points in less than 4 hours on a low-cost machine compared to more than 32 hours with the internal-memory algorithm.
- Agarwal, P. K., Bereg, S., Daescu, O., Kaplan, H., Ntafos, S., and Zhu, B. 2005. Guarding a terrain by two watchtowers. In Proceedings of the ACM Symposium on Computational Geometry. 346--355. Google Scholar
Digital Library
- Aggarwal, A. and Vitter, J. S. 1988. The Input/Output complexity of sorting and related problems. Communications of the ACM 31, 9, 1116--1127. Google ScholarDigital Library
- Ajwani, D., Meyer, U., and Osipov, V. 2007. Improved external memory bfs implementations. In alenex.Google Scholar
- Arge, L. 1997. External-memory algorithms with applications in geographic information systems. In Algorithmic Foundations of GIS, M. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, Eds. Springer-Verlag, LNCS 1340, 213--254. Google ScholarDigital Library
- Arge, L., Barve, R. D., Hutchinson, D., Procopiuc, O., Toma, L., Vahrenhold, J., Vengroff, D. E., and Wickremesinghe, R. 2005. TPIE user manual and reference, edition 1.0. Duke University, NC, “http://www.cs.duke.edu/TPIE/”. (In Preparation).Google Scholar
- Arge, L., Brodal, G. S., and Fagerberg, R. 2005. Cache-oblivious Algorithms. Vol. Handbook of Data Structures and Applications. CRC Press, Chapter 34.Google Scholar
- Arge, L., Toma, L., and Vitter, J. S. 2001. I/O-efficient algorithms for problems on grid-based terrains. ACM J. Experimental Algorithmics 6. Article 1. Google ScholarDigital Library
- Arge, L., Vengroff, D. E., and Vitter, J. S. 1995. External-memory algorithms for processing line segments in geographic information systems. In Proceedings of the European Symposium on Algorithms. LNCS 979. 295--310. Google ScholarDigital Library
- Ben-Moshe, B., Katz, M. J., and Mitchell, J. S. B. 2005. A constant-factor approximation algorithm for optimal terrain guarding. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 515--524. Google ScholarDigital Library
- Brodal, G. S. 2004. Cache-oblivious algorithms and data structures. In Proceedings of the Scandinavian Workshop on Algorithms Theory. LNCS 3111. 3--13.Google ScholarCross Ref
- Brodal, G. S. and Fagerberg, R. 2002. Cache oblivious distribution sweeping. In Proceedings of the International Colloquium on Automata, Languages, and Programming. LNCS 2389. 426--438. Google ScholarDigital Library
- Brodal, G. S., Fagerberg, R., and Vinther, K. 2007. Engineering a cache-oblivious sorting algorithm. J. Exp. Algorithmics 12, 2.2. Google ScholarDigital Library
- Cole, R. and Sharir, M. 1989. Visibility problems for polyhedral terrains. J. Symb. Comput. 7, 1, 11--30. Google ScholarDigital Library
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, 2nd ed. The MIT Press, Cambridge, Mass. Google ScholarDigital Library
- Danner, A. 2007. Private communication.Google Scholar
- de Floriani, L. and Magillo, P. 1994. Visibility algorithms on digital terrain models. International Journal of Geographic Information Systems 8, 1, 13--41.Google ScholarCross Ref
- de Floriani, L. and Magillo, P. 1999. Geographic Information Systems: Principles, Techniques, Managament and Applications. John Wiley and Sons, Chapter Intervisibility of Terrains, 543--556.Google Scholar
- Dementiev, R., Kettner, L., and Sanders, P. 2005. Stxxl: Standard template library for xxl data sets. In Proceedings of the European Symposium on Algorithms. LNCS 3669. 640--651. Google ScholarDigital Library
- Fisher, P. 1993. Algorithm and implementation uncertainty in viewshed analysis. International Journal of GIS 7, 331--347.Google Scholar
- Fisher, P. 1994. Stretching the viewshed. In Proceedings of the Symposium on Spatial Data Handling. 725--738.Google Scholar
- Franklin, W. R. 2002. Siting observers on terrain. In Proceedings of the Symposium on Spatial Data Handling.Google ScholarCross Ref
- Franklin, W. R. and Ray, C. 1994. Higher isn't necessarily better: Visibility algorithms and experiments. In Proceedings of the Symposium on Spatial Data Handling. 751--763.Google Scholar
- Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 285--298. Google ScholarDigital Library
- Goodrich, M. T., Tsay, J.-J., Vengroff, D. E., and Vitter, J. S. 1993. External-memory computational geometry. In Proceedings of the IEEE Symposium on Foundations of Computer Science. 714--723. Google ScholarDigital Library
- Toma, L. 2003. External memory graph algorithms and applications to geographic information systems. Ph.D. thesis, Duke University. Google ScholarDigital Library
- van Kreveld, M. 1996. Variations on sweep algorithms: efficient computation of extended viewsheds and class intervals. In Proceedings of the Symposium on Spatial Data Handling. 15--27.Google Scholar
- van Kreveld, M., Nievergelt, J., Roos, T., and (Eds.), P. W. 1997. Algorithmic Foundations of GIS. LNCS 1340. Springer-Verlag.Google Scholar
Index Terms
- Computing visibility on terrains in external memory
Recommendations
Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane
AbstractWe devise an algorithm for maintaining the visibility polygon of any query point in a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update the data structures that ...
Computing visibility on terrains in external memory
Proceedings of the Meeting on Algorithm Engineering & ExpermimentsWe describe a novel application of the distribution sweeping technique to computing visibility on terrains. Given an arbitrary viewpoint v, the basic problem we address is computing the visibility map or viewshed of v, which is the set of points in the ...
Characterizing and recognizing LR-visibility polygons
A simple polygon P is LR-visible if there are two points s, t on the boundary of P such that every point on the clockwise boundary of P from s to t is visible from some point of the other boundary of P from t to s and vice versa. We show that P is not ...
Reviews
William B Hurst
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. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments