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

Math @ Duke



Publications [#313238] of Pankaj K. Agarwal

Papers Published

  1. Zhang, W; Agarwal, PK; Mukherjee, S, Contour trees of uncertain terrains, GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, vol. 03-06-November-2015 (November, 2015), ISBN 9781450339674 [doi]
    (last updated on 2018/05/26)

    We study contour trees of terrains, which encode the topological changes of the level set of the height value ℓ as we raise ℓ from -∞ to +∞ on the terrains, in the presence of uncertainty in data. We assume that the terrain is represented by a piecewise-linear height function over a planar triangulation M, by specifying the height of each vertex. We study the case when M is fixed and the uncertainty lies in the height of each vertex in the triangulation, which is described by a probability distribution. We present efficient sampling-based Monte Carlo methods for estimating, with high probability, (i) the probability that two points lie on the same edge of the contour tree, within additive error; (ii) the expected distance of two points p; q and the probability that the distance of p; q is at least ℓ on the contour tree, within additive error, where the distance of p; q on a contour tree is defined to be the difference between the maximum height and the minimum height on the unique path from p to q on the contour tree. The main technical contribution of the paper is to prove that a small number of samples are sufficient to estimate these quantities. We present two applications of these algorithms, and also some experimental results to demonstrate the effectiveness of our approach.
ph: 919.660.2800
fax: 919.660.2821

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