Contour trees of uncertain terrains


Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Zhang, W; Agarwal, PK; Mukherjee, S

Published Date

  • November 3, 2015

Published In

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

Volume / Issue

  • 03-06-November-2015 /

International Standard Book Number 13 (ISBN-13)

  • 9781450339674

Digital Object Identifier (DOI)

  • 10.1145/2820783.2820823

Citation Source

  • Scopus