Computing visibility on terrains in external memory

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
146 Downloads (Pure)

Abstract

We 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 terrain that are visible from v. We give the first I/Oefficient algorithm to compute the viewshed of v on a grid terrain in external memory. Our algorithm is based on Van Kreveld’s O(n lg n) time algorithm for the same problem in internal memory. It uses O(sort(n)) I/Os, where sort(n) is the complexity of sorting n items of data in the I/O-model. We present an implementation and experimental evaluation of the algorithm. Our implementation clearly outperforms the previous (in-memory) algorithms and can compute visibility for terrains of up to 4GB in a few hours on a low-cost machine.
Original languageEnglish
Title of host publicationProceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX 2007) 6 January 2007, New Orleans, Louisiana, USA
Place of PublicationPhiladelphia, Pennsylvania, USA
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages13-22
Publication statusPublished - 2007
Event9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007) - Astor Crowne Plaza Hotel, New Orleans, United States
Duration: 6 Jan 20076 Jan 2007
Conference number: 9
http://www.siam.org/meetings/alenex07/

Workshop

Workshop9th Workshop on Algorithm Engineering and Experiments (ALENEX 2007)
Abbreviated titleALENEX 2007
CountryUnited States
CityNew Orleans
Period6/01/076/01/07
OtherEvent preceded the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07)
Internet address

Fingerprint

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

Cite this