Implicit Flow Routing on Triangulated Terrains
Mark de Berg, Herman J. Haverkort, K. Tsirogiannis · 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 Θ(n 2 ) complexity, since at worst case the path can cross Θ(n) triangles for Θ(n) times each. We present a technique for tracing a path of steepest descent on T in O(n log n) time implicitly, without computing all the intersection points of the path with the terrain triangles.