Cited By
View all- Arge LLowe ASvendsen SAgarwal P(2023)1D and 2D Flow Routing on a TerrainACM Transactions on Spatial Algorithms and Systems10.1145/35396609:1(1-39)Online publication date: 12-Jan-2023
1D and 2D Flow Routing on a Terrain
Pages 5 - 14
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 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.
References
[1]
A Aggarwal and JS Vitter. 1988. The input/output complexity of sorting and related problems. Commun. ACM 31, 9 (1988), 1116--1127.
[2]
L Arge, M Rav, S Raza, and M Revsbæk. 2017. I/O-efficient event based depression flood risk. In Proc. 19th Workshop on Algorithm Engineering and Experiments. 259--269.
[3]
L Arge and M Revsbæk. 2009. I/O-efficient contour tree simplification. In Intl. Sympos. on Algos. and Computation. 1155--1165.
[4]
L Arge, M Revsbæk, and N Zeh. 2010. I/O-efficient computation of water flow across a terrain. In Proc. 26th Annu. Sympos. Comp. Geom. 403--412.
[5]
L Arge, L Toma, and J Vitter. 2000. I/O-Efficient algorithms for problems on grid-based terrains. J. Experimental Algorithmics 6 (10 2000). https://doi.org/10.1145/945394.945395
[6]
PD Bates and APJ De Roo. 2000. A simple raster-based model for flood inundation simulation. Journal of hydrology 236, 1--2 (2000), 54--77.
[7]
H Carr, J Snoeyink, and U Axen. 2003. Computing contour trees in all dimensions. Comp. Geom. 24, 2 (2003), 75--94.
[8]
Y Chiang, MT Goodrich, EF Grove, R Tamassia, DE Vengroff, and JS Vitter. 1995. External-memory graph algorithms. In Proc. 6th Annu. ACM-SIAM Sympos. Discrete Algos. 139--149.
[9]
H Edelsbrunner, J Harer, and A Zomorodian. 2001. Hierarchical Morse complexes for piecewise linear 2-manifolds. In Proc. 17th Annu. Sympos. Comp. Geom. 70--79.
[10]
J Holm, E Rotenberg, and M Thorup. 2015. Planar reachability in linear space and constant time. In 2015 IEEE 56th Annual Sympos. Foundations of Computer Science. IEEE, 370--389.
[11]
M Kreveld, R Oostrum, C Bajaj, V Pascucci, and D Schikore. 1997. Contour trees and small seed sets for isosurface traversal. In Proc. 13th Annu. Sympos. Comp. Geom. 212--220.
[12]
Y Liu and J Snoeyink. 2005. Flooding triangulated terrain. In Proc. 11th Intl. Sympos. Spatial Data Handling. 137--148.
[13]
A Lowe and PK Agarwal. 2019. Flood-risk analysis on terrains under the multiflow-direction model. ACM Trans. Spatial Algorithms Syst. 5, 4, Article 26 (Sept. 2019), 27 pages. https://doi.org/10.1145/3340707
[14]
A Lowe, PK Agarwal, and M Rav. 2020. Flood-risk analysis on terrains. Commun. ACM 63, 9 (2020), 94--102. https://dl.acm.org/doi/10.1145/3410413
[15]
A Lowe, SC Svendsen, PK Agarwal, and L Arge. 2020. 1D and 2D Flow Routing on a Terrain. arXiv:2009.08014 [cs.CG]
[16]
R Manning. 1891. On the flow of water in open channels and pipes. Trans. Institution of Civil Engineers of Ireland (1891), 161--207.
[17]
M Rav, A Lowe, and PK Agarwal. 2019. Flood risk analysis on terrains. ACM Trans. Spatial Algorithms and Systems (TSAS) 5, 1 (2019), 1--31.
[18]
P Sanders. 2001. Fast priority queues for cached memory. ACM J. Exp. Algorithmics 5 (Dec. 2001), 7-es. https://doi.org/10.1145/351827.384249
[19]
SCALGO. 2019. www.scalgo.com.
[20]
M Wood, JC Neal, PD Bates, R Hostache, T Wagener, L Giustarini, M Chini, G Corato, and P Matgen. 2016. Calibration of channel depth and friction parameters in the LISFLOOD-FP hydraulic model using medium resolution SAR data and identifiability techniques. Hydrology and Earth System Sciences 20, 12 (2016), 4983--4997.
Index Terms
- 1D and 2D Flow Routing on a Terrain
Recommendations
1D and 2D Flow Routing on a Terrain
An important problem in terrain analysis is modeling how water flows across a terrain creating floods by forming channels and filling depressions. In this article, we study a number of flow-query-related problems: Given a terrain Σ, represented as a ...
Flood-Risk Analysis on Terrains under the Multiflow-Direction Model
An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this article, we study a number of flood-risk related problems: Given a terrain Σ, represented as a triangulated xy-...
Flood Risk Analysis on Terrains
Special Issue on SIGSPATIAL 2017An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this article, we study the flooding query problem: Preprocess a given terrain Σ, represented as a triangulated xy-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2020
687 pages
ISBN:9781450380195
DOI:10.1145/3397536
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 November 2020
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
SIGSPATIAL '20
Sponsor:
SIGSPATIAL '20: 28th International Conference on Advances in Geographic Information Systems
November 3 - 6, 2020
WA, Seattle, USA
Acceptance Rates
Overall Acceptance Rate 257 of 1,238 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 102Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 08 Dec 2024
Other Metrics
Citations
Cited By
View all- Arge LLowe ASvendsen SAgarwal P(2023)1D and 2D Flow Routing on a TerrainACM Transactions on Spatial Algorithms and Systems10.1145/35396609:1(1-39)Online publication date: 12-Jan-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in