DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2020.6

Sea-Rise Flooding on Massive Dynamic Terrains

Authors: Lars Arge, Mathias Rav, Morten Revsbæk, Yujin Shin, and Jungwoo Yang

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract

Predicting floods caused by storm surges is a crucial task. Since the rise of ocean water can create floods that extend far onto land, the flood damage can be severe. By developing efficient flood prediction algorithms that use very detailed terrain models and accurate sea-level forecasts, users can plan mitigations such as flood walls and gates to minimize the damage from storm surge flooding. In this paper we present a data structure for predicting floods from dynamic sea-level forecast data on dynamic massive terrains. The forecast data is dynamic in the sense that new forecasts are released several times per day; the terrain is dynamic in the sense that the terrain model may be updated to plan flood mitigations. Since accurate flood risk computations require using very detailed terrain models, and such terrain models can easily exceed the size of the main memory in a regular computer, our data structure is I/O-efficient, that is, it minimizes the number of I/Os (i.e. block transfers) between main memory and disk. For a terrain represented as a raster of N cells, it can be constructed using O(N/B log_M/B N/B) I/Os, it can compute the flood risk in a given small region using O(log_B N) I/Os, and it can handle updating the terrain elevation in a given small region using O(log²_B N) I/Os, where B is the block size and M is the capacity of main memory.

Cite as

Lars Arge, Mathias Rav, Morten Revsbæk, Yujin Shin, and Jungwoo Yang. Sea-Rise Flooding on Massive Dynamic Terrains. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arge_et_al:LIPIcs.SWAT.2020.6,
  author =	{Arge, Lars and Rav, Mathias and Revsb{\ae}k, Morten and Shin, Yujin and Yang, Jungwoo},
  title =	{{Sea-Rise Flooding on Massive Dynamic Terrains}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.6},
  URN =		{urn:nbn:de:0030-drops-122539},
  doi =		{10.4230/LIPIcs.SWAT.2020.6},
  annote =	{Keywords: Computational geometry, I/O-algorithms, merge tree, dynamic terrain}
}

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 Yang, Jungwoo

Sea-Rise Flooding on Massive Dynamic Terrains

Abstract

Cite as

Maintaining Contour Trees of Dynamic Terrains

Abstract

Cite as

Thanks for your feedback!

Could not send message