Implicit flow routing on triangulated terrains

M.T. Berg, de, H.J. Haverkort, K. Tsirogiannis

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

49 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationAbstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011)
Place of PublicationZürich
PublisherETH Zürich
Publication statusPublished - 2011


Dive into the research topics of 'Implicit flow routing on triangulated terrains'. Together they form a unique fingerprint.

Cite this