Computing visibility on terrains in external memory

H.J. Haverkort, L. Toma, Yi Zhuang

Research output: Contribution to journalArticleAcademicpeer-review

26 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)1-23
JournalJournal on Experimental Algorithmics
Volume13
Issue number5
DOIs
Publication statusPublished - 2008

Fingerprint Dive into the research topics of 'Computing visibility on terrains in external memory'. Together they form a unique fingerprint.

  • Cite this