Title:

Maintaining contour tree of Dynamic terrains

Abstract:

We consider maintaining the contour tree T of a piecewise-linear triangulation M that is the graph of a time varying height function h : R^2 ? R.

In this talk, we describe the combinatorial change in T that happen as h varies over time and how these changes relate to topological changes in M.

Also, we present a kinetic data structure that maintains the contour tree of M over time. Our data structure maintains certificates that fail only when h(v) = h(u) for two adjacent vertices v and u in M, or when saddle vertices lie on the same contour of M. A certificate failure is handled in O(log(n)) time.

Joint work with

Pankaj Agarwal, Lars Arge, Thomas Mølhave, and Morten Revsbæk.