Computing highly occluded paths using a sparse network
Computing paths over a terrain that are highly occluded with respect to observers is an important problem in GIS. Given a fast algorithm for computing the visibility map, the path-planning step becomes the bottleneck. In this paper, we present an approach for quickly computing occluded paths over a terrain using a sparse network, a sparse 1-dimensional network over the terrain. We present different strategies for constructing the sparse network. Experimental results show that our approach results in significantly improved time for computing highly occluded paths between two query points, and that the different strategies offer a tradeoff between higher-quality paths and lower preprocessing times. Further- more, there are strategies that achieve near-optimal paths with small preprocessing cost.
Lebeck, N; Mølhave, T; Agarwal, PK
Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems
Volume / Issue
Start / End Page
International Standard Book Number 13 (ISBN-13)
Digital Object Identifier (DOI)