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.
|Title of host publication||Proceedings 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'11, San Francisco CA, USA, January 23-25, 2011)|
|Publisher||Society for Industrial and Applied Mathematics (SIAM)|
|Publication status||Published - 2011|