License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.6
URN: urn:nbn:de:0030-drops-122539
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12253/
Go to the corresponding LIPIcs Volume Portal


Arge, Lars ; Rav, Mathias ; Revsbæk, Morten ; Shin, Yujin ; Yang, Jungwoo

Sea-Rise Flooding on Massive Dynamic Terrains

pdf-format:
LIPIcs-SWAT-2020-6.pdf (0.9 MB)


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.

BibTeX - Entry

@InProceedings{arge_et_al:LIPIcs:2020:12253,
  author =	{Lars Arge and Mathias Rav and Morten Revsbæk and Yujin Shin and Jungwoo Yang},
  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 =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12253},
  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}
}

Keywords: Computational geometry, I/O-algorithms, merge tree, dynamic terrain
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI