1D and 2D Flow Routing on a Terrain
Aaron Lowe, Svend C. Svendsen, Pankaj K. Agarwal, Lars Arge · 2020
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, and 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: