MADALGO seminar

MADALGO theory seminar, Jungwoo Yang, MADALGO

2014.09.22 | Katrine Østerlund Rasmussen

Date Wed 24 Sep
Time 14:15 15:00
Location Building 5335, Nygaard-395


Maintaining contour tree of Dynamic terrains


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.