Implicit flow routing on terrains with applications to surface networks and drainage structures

Flow-related structures on terrains are defined in terms of paths of steepest descent (or ascent). A steepest descent path on a polyhedral terrain T with n vertices can have T(n^2) complexity. The watershed of a point p --- the set of points on T whose paths of steepest descent reach p --- can have complexity T(n^3). We present a technique for tracing a collection of n paths of steepest descent on T implicitly in O(n logn) time. We then derive O(n log n) time algorithms for: (i) computing for each local minimum p of T the triangles contained in the watershed of p and (ii) computing the surface network graph of T. We also present an O(n^2) time algorithm that computes the watershed area for each local minimum of T.