More Web Proxy on the site http://driver.im/

research-article

I/O-efficient computation of water flow across a terrain

Authors:

Morten Revsbaek,

Norbert ZehAuthors Info & Claims

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

Pages 403 - 412

https://doi.org/10.1145/1810959.1811026

Published: 13 June 2010 Publication History

Abstract

Consider rain falling at a uniform rate onto a terrain T represented as a triangular irregular network. Over time, water collects in the basins of T, forming lakes that spill into adjacent basins. Our goal is to compute, for each terrain vertex, the time this vertex is flooded (covered by water). We present an I/O-efficient algorithm that solves this problem using O(sort(X) log (X/M) + sort(N)) I/Os, where N is the number of terrain vertices, X is the number of pits of the terrain, sort(N) is the cost of sorting N data items, and M is the size of the computer's main memory. Our algorithm assumes that the volumes and watersheds of the basins of T have been precomputed using existing methods.

References

[1]

P. Agarwal, L. Arge, and K. Yi. I/O-efficient batched union-find and its applications to terrain analysis. In Proc. 22nd SCG, pp. 167--176, 2006.

Digital Library

[2]

A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Comm. of the ACM, 31(9):1116--1127, 1988.

Digital Library

[3]

L. Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1--24, 2003.

Digital Library

[4]

L. Arge, J. Chase, P. Halpin, L. Toma, D. Urban, J. S. Vitter, and R. W. and. Flow computation on massive grid terrains. In Proc. 9th ACM GIS, pp. 82--87, 2001.

Digital Library

[5]

L. Arge and M. Revsbæ k. I/O-efficient contour tree simplification. In Proc. 20th ISAAC, pp. 1155--1165, 2009.

Digital Library

[6]

Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter. External-memory graph algorithms. In Proc. 6th SODA, pp. 139--149, 1995.

Digital Library

[7]

A. Danner. I/O Efficient Algorithms and Applications in Geographic Information Systems. PhD thesis, Dept. of Comp. Sci., Duke University, 2006.

Digital Library

[8]

A. Danner, K. Yi, T. Mølhave, P. K. Agarwal, L. Arge, and H. Mitasova. TerraStream: From elevation data to watershed hierarchies. Manuscript, 2007.

[9]

M. de Berg, O. Cheong, H. Haverkort, J.-G. Lim, and L. Toma. I/O-efficient flow modelling on fat terrains. In Proc. 10th WADS, pp. 239--250, 2007.

Digital Library

[10]

H. Edelsbrunner, J. Harer, and A. Zomorodian. Hierarchical morse complexes for piecewise linear 2-manifolds. In Proc. 17th SCG, pp. 70--79, 2001.

Digital Library

[11]

H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. In Proc. 41st FOCS, pp. 454--463, 2000.

Digital Library

[12]

R. Fadel, K. V. Jakobsen, J. Katajainen, and J. Teuhola. Heaps and heapsort on secondary storage. Theor. Comp. Sci., 220(2):345--362, 1999.

Digital Library

[13]

S. Jenson and J. Domingue. Extracting topographic structure from digital elevation data for geographic information system analysis. Photogrammetric Eng. and Remote Sensing, 54(11):1593--1600, 1988.

[14]

Y. Liu and J. Snoeyink. Flooding triangulated terrain. In Proceedings of the 11th International Symposium on Spatial Data Handling, pages 137--148, 2005.

[15]

J. F. O'Callaghan and D. M. Mark. The extraction of drainage networks from digital elevation data. Computer Vision, Graphics and Image Proc., 28(3):323--344, 1984.

[16]

O. Palacios-Velez, W. Gandoy-Bernasconi, and B. Cuevas-Renaud. Geometric analysis of surface runoff and the computation order of unit elements in distributed hydrological models. J. Hydrology, 211:266--274, 1998.

[17]

D. M. Theobald and M. F. Goodchild. Artifacts of TIN-based surface flow modeling. In Proc. GIS/LIS'90, pp. 955--964, 1990.

[18]

G. Tucker, S. Lancaster, N. Gasparini, and S. Rybarczyk. An object-oriented framework for hydrology and geomorphic modeling using triangulated irregular networks. Computers and Geosciences, 27(8):959--973, 2001.

Digital Library

Cited By

Zhao GBalstrøm TMark OJensen M(2021)Multi-Scale Target-Specified Sub-Model Approach for Fast Large-Scale High-Resolution 2D Urban Flood ModellingWater10.3390/w1303025913:3(259)Online publication date: 21-Jan-2021
https://doi.org/10.3390/w13030259
Johnsson IBalstrøm T(2021)A GIS-based Screening Method to Identify Climate Change-Related Threats on Road Networks: A Case Study from SwedenClimate Risk Management10.1016/j.crm.2021.100344(100344)Online publication date: Jul-2021
https://doi.org/10.1016/j.crm.2021.100344
Lowe ASvendsen SAgarwal PArge L(2020)1D and 2D Flow Routing on a TerrainProceedings of the 28th International Conference on Advances in Geographic Information Systems10.1145/3397536.3422269(5-14)Online publication date: 3-Nov-2020
https://dl.acm.org/doi/10.1145/3397536.3422269
Show More Cited By

Index Terms

I/O-efficient computation of water flow across a terrain
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Flood Risk Analysis on Terrains
Special Issue on SIGSPATIAL 2017

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 the flooding query problem: Preprocess a given terrain Σ, represented as a triangulated xy-...
Flood Risk Analysis on Terrains
SIGSPATIAL '17: Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this paper we study the flooding query problem: Given a rain region R and a query point q on the terrain, quickly ...
Efficient Debris-flow Simulation for Steep Terrain Erosion

Erosion simulation is a common approach used for generating and authoring mountainous terrains. While water is considered the primary erosion factor, its simulation fails to capture steep slopes near the ridges. In these low-drainage areas, erosion is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SoCG '10: Proceedings of the twenty-sixth annual symposium on Computational geometry

June 2010

452 pages

ISBN:9781450300162

DOI:10.1145/1810959

Program Chairs:
David Kirkpatrick
University of British Columbia, Canada
,
Joseph Mitchell
SUNY Stony Brook, USA

Copyright © 2010 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 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '10

Sponsor:

SoCG '10: Symposium on Computational Geometry

June 13 - 16, 2010

Utah, Snowbird, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
278
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhao GBalstrøm TMark OJensen M(2021)Multi-Scale Target-Specified Sub-Model Approach for Fast Large-Scale High-Resolution 2D Urban Flood ModellingWater10.3390/w1303025913:3(259)Online publication date: 21-Jan-2021
https://doi.org/10.3390/w13030259
Johnsson IBalstrøm T(2021)A GIS-based Screening Method to Identify Climate Change-Related Threats on Road Networks: A Case Study from SwedenClimate Risk Management10.1016/j.crm.2021.100344(100344)Online publication date: Jul-2021
https://doi.org/10.1016/j.crm.2021.100344
Lowe ASvendsen SAgarwal PArge L(2020)1D and 2D Flow Routing on a TerrainProceedings of the 28th International Conference on Advances in Geographic Information Systems10.1145/3397536.3422269(5-14)Online publication date: 3-Nov-2020
https://dl.acm.org/doi/10.1145/3397536.3422269
Wu YWu XChen L(2020)Point Flood Query Based on Fast Binary Merge TreeProceedings of the 2020 3rd International Conference on Geoinformatics and Data Analysis10.1145/3397056.3397075(38-42)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3397056.3397075
Beschastnikh ILiu PXing AWang PBrun YErnst M(2020)Visualizing Distributed System ExecutionsACM Transactions on Software Engineering and Methodology10.1145/337563329:2(1-38)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1145/3375633
Lowe AAgarwal P(2019)Flood-Risk Analysis on Terrains under the Multiflow-Direction ModelACM Transactions on Spatial Algorithms and Systems10.1145/33407075:4(1-27)Online publication date: 18-Sep-2019
https://dl.acm.org/doi/10.1145/3340707
Schoenebeck GTao B(2019)Beyond Worst-case (In)approximability of Nonsubmodular Influence MaximizationACM Transactions on Computation Theory10.1145/331390411:3(1-56)Online publication date: 2-Apr-2019
https://dl.acm.org/doi/10.1145/3313904
Rav MLowe AAgarwal P(2019)Flood Risk Analysis on TerrainsACM Transactions on Spatial Algorithms and Systems10.1145/32954595:1(1-31)Online publication date: 5-Jun-2019
https://dl.acm.org/doi/10.1145/3295459
Hsu CDeng QMars JTang L(2018)SmoothOperatorACM SIGPLAN Notices10.1145/3296957.317319053:2(535-548)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3173190
Mishra NImes CLafferty JHoffmann H(2018)CALOREEACM SIGPLAN Notices10.1145/3296957.317318453:2(184-198)Online publication date: 19-Mar-2018
https://dl.acm.org/doi/10.1145/3296957.3173184
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten