Implicit flow routing on triangulated terrains

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

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

38 Downloads (Pure)

Abstract

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
Pages151-154
Publication statusPublished - 2011

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

Cite this