Aarhus University Seal / Aarhus Universitets segl

MADALGO seminar

MADALGO theory seminar, Jungwoo Yang, MADALGO

Info about event


Wednesday 24 September 2014,  at 14:15 - 15:00


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.