文章基本信息

标题：Sea-Rise Flooding on Massive Dynamic Terrains
本地全文：下载
作者：Lars Arge ; Mathias Rav ; Morten RevsbÃ¦k 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：162
页码：6:1-6:19
DOI：10.4230/LIPIcs.SWAT.2020.6
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Computational geometry; I/O-algorithms; merge tree; dynamic terrain