1D and 2D Flow Routing on a Terrain
| Autor: | Pankaj K. Agarwal, Aaron Lowe, Lars Arge, Svend C. Svendsen |
|---|---|
| Přispěvatelé: | Lu, Chang-Tien, Wang, Fusheng, Trajcevski, Goce, Huang, Yan, Newsam, Shawn, Xiong, Li |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Surface (mathematics) Terrains Computer science Terrain Function (mathematics) Data structure hydrological modeling Computer Science Applications Flow (mathematics) Modeling and Simulation Signal Processing Path (graph theory) Computer Science - Computational Geometry Discrete Mathematics and Combinatorics Geometry and Topology flood-risk analysis river-network extraction Algorithm Flow routing Information Systems Communication channel |
| Zdroj: | Lowe, A, Svendsen, S C, Agarwal, P K & Arge, L 2020, 1D and 2D Flow Routing on a Terrain . in C-T Lu, F Wang, G Trajcevski, Y Huang, S Newsam & L Xiong (eds), Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 . Association for Computing Machinery, GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, pp. 5-14, 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020, Virtual, Online, United States, 03/11/2020 . https://doi.org/10.1145/3397536.3422269 SIGSPATIAL/GIS Arge, L, Lowe, A, Svendsen, S C & Agarwal, P K 2023, ' 1D and 2D Flow Routing on a Terrain ', ACM Transactions on Spatial Algorithms and Systems, vol. 9, no. 1, 3 . https://doi.org/10.1145/3539660 |
| Popis: | 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 $\Sigma$, 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 $\Sigma$ 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 $\Sigma$ in $O(\rho k+|\phi| \log n)$ time, where $\rho$ is the number of sinks in $\Sigma$, $k$ is the number of times the rain distribution changes, and $|\phi|$ 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 $\Sigma$ 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(\text{Sort}(|\phi|))$ I/Os and $O(|\phi| \log |\phi|)$ internal computation time. (iii) $\Sigma$ 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) \in \Sigma$ 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. Comment: 12 pages, to be published in SIGSPATIAL'20 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|