Flow Computations on Imprecise Terrains

Details Flow Computations on Imprecise Terrains Flow Computations on Imprecise Terrains

2011-11-07

arxiv.org/abs/1111.1651v1

Computer Science

Computational Geometry

Scientific paper

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 flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predefined graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x,y)-coordinates are fixed. For the first model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time.

Affiliated with

Also associated with

No associations

Rating

Flow Computations on Imprecise Terrains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Flow Computations on Imprecise Terrains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flow Computations on Imprecise Terrains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692910