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(n2) complexity, since at worst case the path can cross T(n) triangles for T(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.
|Title of host publication||Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011)|
|Place of Publication||Zürich|
|Publication status||Published - 2011|