publication . Conference object . Part of book or chapter of book . Article . 2007

Computing visibility on terrains in external memory

Haverkort, H.J.; Toma, L.; Zhuang, Yi;
Open Access English
  • Published: 06 Jan 2007
  • Publisher: Society for Industrial and Applied Mathematics (SIAM)
  • Country: Netherlands
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 ...
Subjects
free text keywords: Theoretical Computer Science
Related Organizations
Download fromView all 4 versions
Repository TU/e
Conference object . 2007
Provider: NARCIS
http://pdfs.semanticscholar.or...
Part of book or chapter of book
Provider: UnpayWall
Repository TU/e
Article . 2008
Provider: NARCIS

[2] P. K. Agarwal, S. Bereg, O. Daescu, H. Kaplan, S. Ntafos, and B. Zhu. Guarding a terrain by two watchtowers. In SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry, pages 346-355, 2005.

[3] A. Aggarwal and J. S. Vitter. The Input/Output complexity of sorting and related problems. Communications of the ACM, 31(9):1116-1127, 1988. [OpenAIRE]

[12] L. de Floriani and P. Magillo. Visibility algorithms on digital terrain models. International Journal of Geographic Information Systems, 8(1):13-41, 1994.

[13] P. Fisher. Algorithm and implementation uncertainty in viewshed analysis. International Journal of GIS, 7:331-347, 1993.

[14] P. Fisher. Stretching the viewshed. In Proc. Symposium on Spatial Data Handling, pages 725- 738, 1994.

[4] L. Arge. External-memory algorithms with applications in geographic information systems. In M. van Kreveld, J. Nievergelt, T. Roos, and [16] W. R. Franklin and C. Ray. Higher isn't necessarily P. Widmayer, editors, Algorithmic Foundations of better: Visibility algorithms and experiments. In GIS, pages 213-254. Springer-Verlag, LNCS 1340, Proc. Symposium on Spatial Data Handling, pages 1997. 751-763, 1994.

[15] W. R. Franklin. Siting observers on terrain. In Proc. Symposium on Spatial Data Handling, 2002.

[5] L. Arge, D. E. Vengroff, and J. S. Vitter. External- [17] M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and memory algorithms for processing line segments in J. S. Vitter. External-memory computational geographic information systems. In Proc. European geometry. In Proc. IEEE Symposium on FoundaSymposium on Algorithms, LNCS 979, pages 295- tions of Computer Science, pages 714-723, 1993. 310, 1995.

[6] L. Arge, L. Toma, and J. S. Vitter. I/O-efficient algorithms for problems on grid-based terrains. ACM J. Experimental Algorithmics, 6, 2001. Article 1. [OpenAIRE]

[7] L. Arge, R. D. Barve, D. Hutchinson, O. Procopiuc, L. Toma, J. Vahrenhold, D. E. Vengroff, and R. Wickremesinghe. TPIE user manual and reference, edition 1.0. Duke University, NC, ”http://www.cs.duke.edu/TPIE/”, 2005. (In Preparation).

[8] B. Ben-Moshe, M. J. Katz, and J. S. B. Mitchell. A constant-factor approximation algorithm for optimal terrain guarding. In SODA '05: Proceedings

[18] M. van Kreveld. Variations on sweep algorithms: efficient computation of extended viewsheds and class intervals. In Proc. Symposium on Spatial Data Handling, pages 15-27, 1996.

[19] M. van Kreveld, J. Nievergelt, T. Roos, and P. W. (Eds.). Algorithmic Foundations of GIS. LNCS 1340. Springer-Verlag, 1997.

1e+06

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue