Math @ Duke

Publications [#313238] of Pankaj K. Agarwal
Papers Published
 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. 0306November2015
(November, 2015), ISBN 9781450339674 [doi]
(last updated on 2017/12/11)
Abstract: 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 piecewiselinear 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 samplingbased 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.


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

