publication . Preprint . 2018

A Comparison of I/O-Efficient Algorithms for Visibility Computation on Massive Grid Terrains

Haverkort, Herman; Toma, Laura;
Open Access English
  • Published: 03 Oct 2018
Abstract
Comment: 38 pages, 12 figures; This is the full version cumulating two conference papers that appeared in ACM SIGSPATIAL GIS 2009 and ACM SIGSPATIAL GIS 2013. Does not contain new results, only contains more detailed pseudocode, analysis, proofs and plots. Written in 2014/2015. Has not been published and is not under review
Subjects
ACM Computing Classification System: ComputingMethodologies_COMPUTERGRAPHICS
free text keywords: Computer Science - Data Structures and Algorithms
Download from
18 references, page 1 of 2

20 23 25 26 32 46 21 20 24 28 41 46 21 20 24 28 41 46 24 21 23 31 36 36 24 21 23 31 36 36 23 22 24 27 33 34 23 22 24 27 33 34 32 22 29 30 35 34 32 22 29 30 35 34 29 30 33 34 36 37 29 30 33 34 36 37 Aggarwal, A. and Vitter, J. S. 1988. The Input/Output complexity of sorting and related problems. Communications of the ACM 31, 9, 1116{1127. [OpenAIRE]

Andrade, M. V. A., Magalha~es, S. V. G., Magalha~es, M. A., Franklin, W. R., and Cutler, B. M. 2011. E cient viewshed computation on terrain in external memory. Geoinformatica 15, 2, 381{397.

Brodal, G. S., Fagerberg, R., and Vinther, K. 2007. Engineering a cache-oblivious sorting algorithm. J. Exp. Algorithmics 12, 2.2. [OpenAIRE]

Cole, R. and Sharir, M. 1989a. Visibility problems for polyhedral terrains. J. Symb. Comput. 7, 1, 11{30. [OpenAIRE]

Cole, R. and Sharir, M. 1989b. Visibility problems for polyhedral terrains. J. Symbolic Computation 7, 11{30. [OpenAIRE]

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. 2001. Introduction to Algorithms, second ed. The MIT Press, Cambridge, Mass.

de Floriani, L. and Magillo, P. 1994. Visibility algorithms on digital terrain models. International Journal of Geographic Information Systems 8, 1, 13{41.

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.

Ferreira, C. R., Magalha~es, S. V. G., Andrade, M., Franklin, W. R., and Pompermayer, A. M. 2012. More e cient terrain viewshed computation on massive datasets using external memory. In Proc. 20th ACM SIGSPATIAL Symp. Geographic Information Systems (GIS 2012). 169{172.

Fishman, J., Haverkort, H., and Toma, L. 2009. Improved visibility computations on massive grid terrains. In Proc. 17th ACM SIGSPATIAL Symp. Geographic Information Systems (GIS 2009). 121{130. Best paper award. [OpenAIRE]

Franklin, W. R. and Ray, C. 1994. Higher isn't necessarily better: Visibility algorithms and experiments. In Proc. Symposium on Spatial Data Handling. 751{763.

Frigo, M., Leiserson, C. E., Prokop, H., and Ramachandran, S. 1999. Cache-oblivious algorithms. In Proc. IEEE Symposium on Foundations of Computer Science. 285{298.

Hart, S. and Sharir, M. 1986. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica 6, 151{177.

Haverkort, H., Toma, L., and Wei, B. 2013. On io-e cient viewshed algorithms and their accuracy. In Proc. 21st ACM SIGSPATIAL Symp. Geographic Information Systems (GIS 2013). 24{33.

Haverkort, H., Toma, L., and Zhuang, Y. 2008. Computing visibility on terrains in external memory. ACM Journal on Experimental Algorithmics 13, 1.5.1{1.5.23. [OpenAIRE]

18 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue