Computing highly occluded paths using a sparse network

Published

Conference Paper

Copyright 2014 ACM. 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.

Full Text

Duke Authors

Cited Authors

  • Lebeck, N; Mølhave, T; Agarwal, PK

Published Date

  • November 4, 2014

Published In

  • Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems

Volume / Issue

  • 04-07-November-2014 /

Start / End Page

  • 3 - 12

International Standard Book Number 13 (ISBN-13)

  • 9781450331319

Digital Object Identifier (DOI)

  • 10.1145/2666310.2666394

Citation Source

  • Scopus