Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Final published version
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: (i) An internal-memory algorithm for answering terrain-flow queries: preprocess Σ into a linear-size data structure so that given a rain distribution R the flow-rate functions of all edges of Σ can be reported quickly. (ii) I/O-efficient algorithms for answering terrain-flow queries. (iii) An internal memory algorithm for answering edge-flow queries: preprocess Σ into a linear-size data structure so that given a rain distribution R, the flow-rate function of an edge under the single-flow direction (SFD) model can be computed quickly. (iv) We present an efficient algorithm that given a path in Σ computes the two-dimensional channel along which water flows.
Original language | English |
---|---|
Title of host publication | Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 |
Editors | Chang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn Newsam, Li Xiong |
Publisher | Association for Computing Machinery |
Publication year | Nov 2020 |
Pages | 5-14 |
ISBN (Electronic) | 9781450380195 |
DOIs | |
Publication status | Published - Nov 2020 |
Event | 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 - Virtual, Online, United States Duration: 3 Nov 2020 → 6 Nov 2020 |
Conference | 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 |
---|---|
Land | United States |
By | Virtual, Online |
Periode | 03/11/2020 → 06/11/2020 |
Sponsor | Apple, Esri, Google, Oracle |
Series | GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems |
---|
See relations at Aarhus University Citationformats
ID: 202723859