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 ScholarDigital 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 ...
Comments