DROPS

Document

DOI: 10.4230/LIPIcs.SOCG.2015.796

Maintaining Contour Trees of Dynamic Terrains

Authors: Pankaj K. Agarwal, Thomas Mølhave, Morten Revsbæk, Issam Safa, Yusu Wang, and Jungwoo Yang

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

We study the problem of maintaining the contour tree 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 T and how they relate to topological changes in Sigma. We present a kinetic data structure (KDS) for maintaining 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 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.

Cite as

Pankaj K. Agarwal, Thomas Mølhave, Morten Revsbæk, Issam Safa, Yusu Wang, and Jungwoo Yang. Maintaining Contour Trees of Dynamic Terrains. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 796-811, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SOCG.2015.796,
  author =	{Agarwal, Pankaj K. and M{\o}lhave, Thomas and Revsb{\ae}k, Morten and Safa, Issam and Wang, Yusu and Yang, Jungwoo},
  title =	{{Maintaining Contour Trees of Dynamic Terrains}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{796--811},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.796},
  URN =		{urn:nbn:de:0030-drops-51406},
  doi =		{10.4230/LIPIcs.SOCG.2015.796},
  annote =	{Keywords: Contour tree, dynamic terrain, kinetic data structure}
}

Search Results

Documents authored by Safa, Issam

Maintaining Contour Trees of Dynamic Terrains

Abstract

Cite as

Thanks for your feedback!

Could not send message