## Flow Computations on Imprecise Terrains

We study the computation of the flow of water on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water can only flow along the edges of a predefined graph (for example a grid, a triangulation, or its dual), and one where water flows across the surface of a polyhedral terrain in the direction of steepest descent. In both cases each vertex has an imprecise height, given by an interval of possible values, while its (x,y)-coordinates are fixed. For the first model, we give a simple O(n log n) time algorithm to compute the maximal watershed of a vertex. We show that, in contrast, in the second model the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard.

keywords: Computational Geometry, Geographical Information Analysis, Data Imprecision, Terrains

### Journal Article (peer-reviewed)

Anne Driemel, Herman Haverkort, Maarten Löffler, Rodrigo I. Silveira

Flow Computations on Imprecise Terrains

Journal of Computational Geometry

4, 1, 38–78, 2013

### Conference Proceedings (peer-reviewed)

Anne Driemel, Herman Haverkort, Maarten Löffler, Rodrigo I. Silveira

Flow Computations on Imprecise Terrains

Proc. 12th Algorithms and Data Structures Symposium

350–361, 2011

### Workshop or Poster (weakly reviewed)

Anne Driemel, Herman Haverkort, Maarten Löffler, Rodrigo I. Silveira

Flow Computations on Imprecise Terrains

Proc. 27th European Workshop on Computational Geometry

119–122, 2011

### Archived Publication (not reviewed)

Anne Driemel, Herman Haverkort, Maarten Löffler, Rodrigo I. Silveira

Flow Computations on Imprecise Terrains

1111.1651, 2011

back to list