Document Open Access Logo

Maintaining Contour Trees of Dynamic Terrains

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

PDF
Thumbnail PDF

File

LIPIcs.SOCG.2015.796.pdf
  • Filesize: 1.16 MB
  • 16 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.SOCG.2015.796

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.

Subject Classification

Keywords
  • Contour tree
  • dynamic terrain
  • kinetic data structure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. K. Agarwal, L. Arge, T. M. Murali, Kasturi R. Varadarajan, and J. S. Vitter. I/O-efficient algorithms for contour-line extraction and planar graph blocking. In Proc. 9th ACM-SIAM Sympos. Discrete Algorithms, pages 117-126, 1998. Google Scholar
  2. P. K. Agarwal and M. Sharir. Davenport-Schinzel sequences and their geometric applications. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 1-47. Elsevier Science Publishers, 2000. Google Scholar
  3. Pankaj K. Agarwal, Lars Arge, and Ke Yi. I/O-efficient batched union-find and its applications to terrain analysis. In Proc. 22nd Annu. Sympos. Comput. Geom., pages 167-176, 2006. Google Scholar
  4. Lars Arge, Morten Revsbæk, and Norbert Zeh. I/O-efficient computation of water flow across a terrain. In Proc. 26th Annu. Sympos. Comput. Geom., pages 403-412, 2010. Google Scholar
  5. J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data. J. Algorithms, 31(1):1-28, 1999. Google Scholar
  6. K.G. Bemis, D. Silver, P.A. Rona, and C. Feng. Case study: a methodology for plume visualization with application to real-time acquisition and navigation. In Proc. IEEE Conf. Visualization, pages 481-494, 2000. Google Scholar
  7. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008. Google Scholar
  8. Vasco Brattka and Peter Hertling. Feasible real random access machines. J. Complexity, 14(4):490-526, December 1998. Google Scholar
  9. Hamish Carr, Jack Snoeyink, and Ulrike Axen. Computing contour trees in all dimensions. Comput. Geom., 24(2):75-94, 2003. Google Scholar
  10. Hamish Carr, Jack Snoeyink, and Michiel van de Panne. Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree. Comput. Geom., 43(1):42-58, 2010. Google Scholar
  11. A. Danner, T. Mølhave, K. Yi, P. K. Agarwal, L. Arge, and H. Mitásová. Terrastream: From elevation data to watershed hierarchies. In Proc. ACM Sympos. Advances in Geographic Information Systems, page 28, 2007. Google Scholar
  12. Herbert Edelsbrunner, John Harer, Ajith Mascarenhas, Valerio Pascucci, and Jack Snoeyink. Time-varying Reeb graphs for continuous space-time data. Comput. Geom., 41(3):149-166, 2008. Google Scholar
  13. L. Guibas. Modeling motion. In J. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, pages 1117-1134. Chapman and Hall/CRC, 2nd edition, 2004. Google Scholar
  14. Leonidas J. Guibas. Kinetic data structures - a state of the art report. In Proc. Workshop Algorithmic Found. Robot., pages 191-209, 1998. Google Scholar
  15. N. Max, R. Crawfis, and D. Williams. Visualization for climate modeling. IEEE Comput. Graphics and Appl., 13:34-40, 1993. Google Scholar
  16. Daniel D. Sleator and Robert E. Tarjan. A data structure for dynamic trees. J. Comput. Sys. Sci., 26(3):362-391, 1983. Google Scholar
  17. B. S. Sohn and Bajaj C. L. Time-varying contour topology. IEEE Transactions on Visualization and Computer Graphics, 12(1):14-25, 2006. Google Scholar
  18. A. Szymczak. Subdomain aware contour trees and contour evolution in time-dependent scalar fields. In Proc. Conf. Shape Model. and Appl., pages 136-144, 2005. Google Scholar
  19. S. P. Tarasov and M. N. Vyalyi. Construction of contour trees in 3D in O(n log n) steps. In Proc. 14th Annu. Sympos. Comput. Geom., pages 68-75, 1998. Google Scholar
  20. M. van Kreveld, R. van Oostrum, C. Bajaj, V. Pascucci, and D. Schikore. Contour trees and small seed sets for isosurface traversal. In Proc. 13th Annu. Sympos. Comput. Geom., pages 212-220, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact