The complexity of river networks on realistic terrains

Abstract

We study the flow of water on \\\\textit{fat terrains}, that is, triangulated terrains where the minimum angle of any triangle is bounded from below by a positive constant. The river network of a terrain is the set of points on which the watershed has nonzero area. We show that the worst-case complexity of the river network on such terrains is $\\\\Theta(n^2)$. This improves the corresponding bounds for arbitrary terrains by a linear factor. We prove that in general similar bounds cannot be proven for Delaunay triangulations: these can have river networks of complexity $\\\\Theta(n^3)$.