Flood-risk analysis on terrains under the multiflow-direction model


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 a number of flood-risk related problems: Given a terrain Σ, represented as a triangulated xy-monotone surface with n vertices, a rain distribution R, and a volume of rain ψ, determine which portions of Σ are flooded. We develop efficient algorithms for flood-risk analysis under the multiflow-directions (MFD) model, in which water at a point can flow along multiple downslope edges and which more accurately represent flooding events. We present three main results: First, we present an O (n log n)-time algorithm to answer a terrain-flood query: if it rains a volume ψ according to a rain distribution R, determine what regions of Σ will be flooded. Second, we present a O (n log n + nm)-time algorithm for preprocessing Σ containing m sinks into a data structure of size O (nm) for answering point-flood queries: Given a rain distribution R, a volume of rain ψ falling according to R, and point q ∈ Σ, determine whether q will be flooded. A point-flood query can be answered in O (|R |k + k2 ) time, where k is the number of maximal depressions in Σ containing the query point q and |R | is the number of vertices in R with positive rainfall. Finally, we present algorithms for answering a flood-time query: given a rain distribution R and a point q ∈ Σ, determine the volume of rain that must fall before q is flooded. Assuming that the product of two k × k matrices can be computed in O (kω ) time, we show that a flood-time query can be answered in O (nk + kω ) time. We also give an α -approximation algorithm, for α > 1, which runs in O (n log n logα ρ)-time, where ρ is a variable on the terrain that depends on the ratio between depression volumes. We implemented our algorithms for computing terrain and point-flood queries as well as approximate flood-time queries. We tested the efficacy and efficiency of these algorithms on three real terrains of different types (urban, suburban, and mountainous.)

Full Text

Duke Authors

Cited Authors

  • Lowe, A; Agarwal, PK

Published Date

  • September 1, 2019

Published In

Volume / Issue

  • 5 / 4

Electronic International Standard Serial Number (EISSN)

  • 2374-0361

International Standard Serial Number (ISSN)

  • 2374-0353

Digital Object Identifier (DOI)

  • 10.1145/3340707

Citation Source

  • Scopus