1D and 2D Flow Routing on a Terrain
share
An important problem in terrain analysis is modeling how water flows across a terrain creating floods by forming channels and filling depressions. In this paper we study a number of flow-query related problems: Given a terrain Σ, represented as a triangulated xy-monotone surface with n vertices, a rain distribution R which may vary over time, determine how much water is flowing over a given edge as a function of time. We develop internal-memory as well as I/O-efficient algorithms for flow queries. This paper contains four main results: (i) We present an internal-memory algorithm that preprocesses Σ into a linear-size data structure that for a (possibly time varying) rain distribution R can return the flow-rate functions of all edges of Σ in O(ρ k+|ϕ| log n) time, where ρ is the number of sinks in Σ, k is the number of times the rain distribution changes, and |ϕ| is the total complexity of the flow-rate functions that have non-zero values; (ii) We also present an I/O-efficient algorithm for preprocessing Σ into a linear-size data structure so that for a rain distribution R, it can compute the flow-rate function of all edges using O(Sort(|ϕ|)) I/Os and O(|ϕ| log |ϕ|) internal computation time. (iii) Σ can be preprocessed into a linear-size data structure so that for a given rain distribution R, the flow-rate function of an edge (q,r) ∈Σ under the single-flow direction (SFD) model can be computed more efficiently. (iv) We present an algorithm for computing the two-dimensional channel along which water flows using Manning's equation; a widely used empirical equation that relates the flow-rate of water in an open channel to the geometry of the channel along with the height of water in the channel.
READ FULL TEXT