i/o-efficient computation of water flow across a terrain
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.
terrains i/o-efficient algorithms geographical information systems