Flood risk analysis on terrains

Published

Journal Article

© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. 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-monotone surface with n vertices, into a data structure so that for a query rain region R and a query point q on Σ, one can quickly determine how much rain has to fall in R so that q is flooded. Available terrain data is often subject to uncertainty, which must be incorporated into the terrain analysis. For instance, the digital elevation models of terrains have to be refined to incorporate underground pipes, tunnels, and waterways under bridges, but there is often uncertainty in their existence. By representing the uncertainty in the terrain data explicitly, we can develop methods for flood risk analysis that properly incorporate terrain uncertainty when reporting what areas are at risk of flooding. We present two results. First, we present an O(n log n)-time algorithm for preprocessing Σ with a linear-size data structure that can answer a flooding query in O(|R| + m log n) time, where |R| is the number of vertices in R, m is the number of so-called tributaries of q at which rain is falling, and n is the number of vertices of the terrain. Next, we extend this data structure to handle “uncertain” terrains using a standard Monte Carlo method. Given a probability distribution on terrain data, our data structure returns the probability of a query point being flooded if a specified amount of rain falls on a query region. We implement our data structure and test it on real terrains, showing that a small number of samples suffice to accurately estimate the flood risk.

Full Text

Duke Authors

Cited Authors

  • Rav, M; Lowe, A; Agarwal, PK

Published Date

  • May 1, 2019

Published In

Volume / Issue

  • 5 / 1

Electronic International Standard Serial Number (EISSN)

  • 2374-0361

International Standard Serial Number (ISSN)

  • 2374-0353

Digital Object Identifier (DOI)

  • 10.1145/3295459

Citation Source

  • Scopus