2012.01.25

Title: Flow Modelling on Triangulated Terrains: Computational Problems in Theory and Practice

Speaker: Constantinos Tsirogiannis, Aarhus University

Abstract:
One of the most popular ways to represent a terrain is the Triangulated Irregular Network (TIN), that is a 2D triangulation where each vertex has also an elevation value. The natural way of modelling water flow on a triangulated terrain is to make the simple assumption that water follows the direction of steepest descent. Using this assumption, it is possible to design algorithms for constructing drainage structures on a TIN, such as watersheds. Unfortunately, there exist instances of TINs for which the combinatorial complexity of drainage structures is very high.

In this presentation we describe the main computational problems that arise, both in theory and in practice, when attempting to construct drainage structures on TINs. We present efficient algorithms that extract information on the drainage structures of a TIN without explicitly computing those structures themselves. We also provide experimental results that show which are the actual bottlenecks that appear when using this flow-modelling in practice.

This presentation summarizes results from joint works with Mark de Berg and Herman Haverkort

Host: Gerth Stølting Brodal