1D and 2D Flow Routing on a Terrain
arXiv:2009.08014 · doi:10.1145/3397536.3422269
Abstract
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 \emph{flow-query} related problems: Given a terrain , represented as a triangulated -monotone surface with vertices, a rain distribution 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 can return the flow-rate functions of all edges of in time, where is the number of sinks in , 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 , it can compute the flow-rate function of all edges using I/Os and internal computation time. (iii) can be preprocessed into a linear-size data structure so that for a given rain distribution , the flow-rate function of an edge 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.
12 pages, to be published in SIGSPATIAL'20