Aarhus University Seal / Aarhus Universitets segl

1D and 2D Flow Routing on a Terrain

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

DOI

  • Aaron Lowe, Duke University
  • ,
  • Svend C. Svendsen
  • Pankaj K. Agarwal, Duke University
  • ,
  • Lars Arge

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 languageEnglish
Title of host publicationProceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020
EditorsChang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn Newsam, Li Xiong
PublisherAssociation for Computing Machinery
Publication yearNov 2020
Pages5-14
ISBN (Electronic)9781450380195
DOIs
Publication statusPublished - Nov 2020
Event28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 - Virtual, Online, United States
Duration: 3 Nov 20206 Nov 2020

Conference

Conference28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020
LandUnited States
ByVirtual, Online
Periode03/11/202006/11/2020
SponsorApple, Esri, Google, Oracle
SeriesGIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

    Research areas

  • flood-risk analysis, hydrological modeling, river-network extraction, Terrains

See relations at Aarhus University Citationformats

ID: 202723859