Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Maintaining Contour Trees of Dynamic Terrains

Research output: Working paperResearch

  • Pankaj K. Agarwal, Department of Computer Science, Duke University, United States
  • Lars Arge
  • Thomas Mølhave, Duke University, United States
  • Morten Revsbæk, Denmark
  • Jungwoo Yang, Denmark
We consider maintaining the contour tree T of a piecewise-linear triangulation M that is the graph of a time varying height function h:R2→R. We carefully describe the combinatorial change in T that happen as h varies over time and how these changes relate to topological changes in M. We present a kinetic data structure that maintains the contour tree of h 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 two saddle vertices lie on the same contour of M. A certificate failure is handled in O(log(n)) time. We also show how our data structure can be extended to handle a set of general update operations on M and how it can be applied to maintain topological persistence pairs of time varying functions.
Original languageEnglish
PublisherCornell University
Number of pages20
Publication statusPublished - 2014

See relations at Aarhus University Citationformats

ID: 81804745