River networks and watershed maps of triangulated terrains revisited

Triangulated surfaces are often used to represent ter- rains in geographic information systems. We investi- gate the complexity of river networks and watershed maps on such terrains under the assumption that wa- ter always follows the path of steepest descent. We show that the worst-case complexity is only ??(n2) if all triangles are non-obtuse or if all triangles are fat, that is, their minimum angles are bounded from below by a positive constant. Furthermore, we can compute the river networks and watershed maps by tracing paths in a directed acyclic graph representa- tion of the triangulation—a property that can be ex- ploited to do computations I/O-efficiently.