×

Maintaining contour trees of dynamic terrains. (English) Zbl 1378.68145

Arge, Lars (ed.) et al., 31st international symposium on computational geometry, SoCG’15, Eindhoven, Netherlands, June 22–25, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-83-5). LIPIcs – Leibniz International Proceedings in Informatics 34, 796-811 (2015).
Summary: We study the problem of maintaining the contour tree \(\mathbb{T}\) of a terrain \(\Sigma\), represented as a triangulated \(xy\)-monotone surface, as the heights of its vertices vary continuously with time. We characterize the combinatorial changes in \(\mathbb{T}\) and how they relate to topological changes in \(\Sigma\). We present a kinetic data structure (KDS) for maintaining \(\mathbb{T}\) efficiently. It maintains certificates that fail, i.e., an event occurs, only when the heights of two adjacent vertices become equal or two saddle vertices appear on the same contour. Assuming that the heights of two vertices of \(\Sigma\) become equal only \(O(1)\) times and these instances can be computed in \(O(1)\) time, the KDS processes \(O(\kappa+n)\) events, where \(n\) is the number of vertices in \(\Sigma\) and \(\kappa\) is the number of events at which the combinatorial structure of \(\mathbb{T}\) changes, and processes each event in \(O(\log n)\) time. The KDS can be extended to maintain an augmented contour tree and a join/split tree.
For the entire collection see [Zbl 1329.68019].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI