Math @ Duke

Publications [#313239] of Pankaj K. Agarwal
Papers Published
 Lebeck, N; MÃ¸lhave, T; Agarwal, PK, Computing highly occluded paths using a sparse network,
GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, vol. 0407November2014
(November, 2014),
pp. 312, ISBN 9781450331319 [doi]
(last updated on 2017/12/16)
Abstract: 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 pathplanning 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 1dimensional 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 higherquality paths and lower preprocessing times. Further more, there are strategies that achieve nearoptimal paths with small preprocessing cost.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

