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

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.