Algorithms Seminar

Flood Risk Analysis on Terrains

Speaker:Aaron Lowe
Date: Thursday, September 14, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this talk, we will examine the flooding query problem: Given a rain region and a query point on the terrain, quickly determine how much rain has to fall in the region so that the query point 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 a linear size data structure that given a terrain (with no data uncertainty) can answer the flooding query in O(m \log^2 n) time, where m is the number of minima of the terrain at which it is raining. Next, we extend this data structure to handle “uncertain”' terrains, using a standard Monte Carlo method. Given a probability distribution on terrains, our data structure solves the problem of determining the probability that a specified amount of rain on a given region will cause a given query point to be flooded. We implement our data structures and show that they work very well in practice.


Aaron Lowe is a 3rd year PhD student here at Duke studying computational geometry with Pankaj Agarwal.