Flood Risk Analysis on Terrains

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.