Implicit flow routing on terrains with applications to surface networks and drainage structures
Mark de Berg, Herman J. Haverkort, Constantinos Tsirogiannis · Symposium on Discrete Algorithms · 2011
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 θ(n2) complexity. The watershed of a point p---the set of points on T whose paths of steepest descent reach p---can have complexity θ(n3). We present a technique for tracing a collection of n paths of steepest descent on T implicitly in O(n log n) 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(n2) time algorithm that computes the watershed area for each local minimum of T.