Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#313239] of Pankaj K. Agarwal

Papers Published

  1. 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. 04-07-November-2014 (November, 2014), pp. 3-12, ISBN 9781450331319 [doi]
    (last updated on 2018/10/14)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320