# Contour trees of uncertain terrains

Published

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