Computing visibility on terrains in external memory

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.

REFERENCES

• 1: 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.
• 2: Aggarwal, A. and Vitter, J. S. 1988. The Input/Output complexity of sorting and related problems. Communications of the ACM 31, 9, 1116--1127.
• 3: Ajwani, D., Meyer, U., and Osipov, V. 2007. Improved external memory bfs implementations. In alenex.
• 4: 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.
• 5: 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).
• 6: Arge, L., Brodal, G. S., and Fagerberg, R. 2005. Cache-oblivious Algorithms. Vol. Handbook of Data Structures and Applications. CRC Press, Chapter 34.
• 7: 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.
• 8: 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.
• 9: 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.
• 10: Brodal, G. S. 2004. Cache-oblivious algorithms and data structures. In Proceedings of the Scandinavian Workshop on Algorithms Theory. LNCS 3111. 3--13.
• 11: 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.
• 12: Brodal, G. S., Fagerberg, R., and Vinther, K. 2007. Engineering a cache-oblivious sorting algorithm. J. Exp. Algorithmics 12, 2.2.
• 13: Cole, R. and Sharir, M. 1989. Visibility problems for polyhedral terrains. J. Symb. Comput. 7, 1, 11--30.
• 14: Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, 2nd ed. The MIT Press, Cambridge, Mass.
• 15: Danner, A. 2007. Private communication.
• 16: de Floriani, L. and Magillo, P. 1994. Visibility algorithms on digital terrain models. International Journal of Geographic Information Systems 8, 1, 13--41.
• 17: 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.
• 18: 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.
• 19: Fisher, P. 1993. Algorithm and implementation uncertainty in viewshed analysis. International Journal of GIS 7, 331--347.
• 20: Fisher, P. 1994. Stretching the viewshed. In Proceedings of the Symposium on Spatial Data Handling. 725--738.
• 21: Franklin, W. R. 2002. Siting observers on terrain. In Proceedings of the Symposium on Spatial Data Handling.
• 22: 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.
• 23: 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.
• 24: 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.
• 25: Toma, L. 2003. External memory graph algorithms and applications to geographic information systems. Ph.D. thesis, Duke University.
• 26: 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.
• 27: van Kreveld, M., Nievergelt, J., Roos, T., and (Eds.), P. W. 1997. Algorithmic Foundations of GIS. LNCS 1340. Springer-Verlag.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.4 Performance Analysis and Design Aids**

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Keywords:
Computational geometry, I/O-efficiency, data structures and algorithms, digital elevation models, terrains, visibility