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.