{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T20:44:00Z","timestamp":1770842640880,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T00:00:00Z","timestamp":1568764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARO","award":["W911NF-15-1-0408"],"award-info":[{"award-number":["W911NF-15-1-0408"]}]},{"name":"U.S.-Israel Binational Science Foundation","award":["2012\/229"],"award-info":[{"award-number":["2012\/229"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-15-13816, CCF-15-46392, and IIS-14-08846"],"award-info":[{"award-number":["CCF-15-13816, CCF-15-46392, and IIS-14-08846"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"\n An important problem in terrain analysis is modeling how water flows across a terrain and creates floods by filling up depressions. In this article, we study a number of\n flood-risk<\/jats:italic>\n related problems: Given a terrain \u03a3, represented as a triangulated\n xy<\/jats:italic>\n -monotone surface with\n n<\/jats:italic>\n vertices, a rain distribution\n R<\/jats:italic>\n , and a volume of rain \u03c8, determine which portions of \u03a3 are flooded. We develop efficient algorithms for flood-risk analysis under the multiflow-directions (MFD) model, in which water at a point can flow along multiple downslope edges and which more accurately represent flooding events.\n <\/jats:p>\n \n We present three main results: First, we present an\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n )-time algorithm to answer a\n terrain-flood<\/jats:italic>\n query: if it rains a volume \u03c8 according to a rain distribution\n R<\/jats:italic>\n , determine what regions of \u03a3 will be flooded. Second, we present a\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n +\n nm<\/jats:italic>\n )-time algorithm for preprocessing \u03a3 containing\n m<\/jats:italic>\n sinks into a data structure of size\n O<\/jats:italic>\n (\n nm<\/jats:italic>\n ) for answering\n point-flood<\/jats:italic>\n queries: Given a rain distribution\n R<\/jats:italic>\n , a volume of rain \u03c8 falling according to\n R<\/jats:italic>\n , and point\n q<\/jats:italic>\n \u2208 \u03a3, determine whether\n q<\/jats:italic>\n will be flooded. A point-flood query can be answered in\n O<\/jats:italic>\n (|\n R<\/jats:italic>\n |\n k<\/jats:italic>\n +\n k<\/jats:italic>\n 2<\/jats:sup>\n ) time, where\n k<\/jats:italic>\n is the number of maximal depressions in \u03a3 containing the query point\n q<\/jats:italic>\n and |\n R<\/jats:italic>\n | is the number of vertices in\n R<\/jats:italic>\n with positive rainfall. Finally, we present algorithms for answering a\n flood-time query<\/jats:italic>\n : given a rain distribution\n R<\/jats:italic>\n and a point\n q<\/jats:italic>\n \u2208 \u03a3, determine the volume of rain that must fall before\n q<\/jats:italic>\n is flooded. Assuming that the product of two\n k<\/jats:italic>\n \u00d7\n k<\/jats:italic>\n matrices can be computed in\n O<\/jats:italic>\n (\n k<\/jats:italic>\n \u03c9<\/jats:sup>\n ) time, we show that a flood-time query can be answered in\n O<\/jats:italic>\n (\n nk<\/jats:italic>\n +\n k<\/jats:italic>\n \u03c9<\/jats:sup>\n ) time. We also give an \u03b1-approximation algorithm, for \u03b1 > 1, which runs in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n log\n n<\/jats:italic>\n log\n \u03b1<\/jats:sub>\n \u03c1)-time, where \u03c1 is a variable on the terrain that depends on the ratio between depression volumes. We implemented our algorithms for computing terrain and point-flood queries as well as approximate flood-time queries. We tested the efficacy and efficiency of these algorithms on three real terrains of different types (urban, suburban, and mountainous.)\n <\/jats:p>","DOI":"10.1145\/3340707","type":"journal-article","created":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T18:35:06Z","timestamp":1568831706000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Flood-Risk Analysis on Terrains under the Multiflow-Direction Model"],"prefix":"10.1145","volume":"5","author":[{"given":"Aaron","family":"Lowe","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137884"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025526421410"},{"key":"e_1_2_1_3_1","volume-title":"Proc. 19th Workshop on Algorithm Engineering and Experiments. 259--269","author":"Arge L."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_116"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1811026"},{"key":"e_1_2_1_6_1","unstructured":"Norwegian Mapping Authority. 2013. Height DTM 10. https:\/\/kartkatalog.geonorge.no\/metadata\/kartverket\/dtm-10-terrengmodell-utm33\/dddbb667-1303-4ac5-8640-7ec04c0e3918. Norwegian Mapping Authority. 2013. Height DTM 10. https:\/\/kartkatalog.geonorge.no\/metadata\/kartverket\/dtm-10-terrengmodell-utm33\/dddbb667-1303-4ac5-8640-7ec04c0e3918."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-1694(00)00278-X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00093-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.009"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jhydrol.2014.07.036"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341012.1341049"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/378583.378626"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2166\/hydro.2012.245"},{"key":"e_1_2_1_14_1","unstructured":"Indiana Spatial Data Portal. 2013. Indiana Orthophotography (RGBI) LiDAR and Elevation. http:\/\/gis.iu.edu\/datasetInfo\/statewide\/in_2011.php. Indiana Spatial Data Portal. 2013. Indiana Orthophotography (RGBI) LiDAR and Elevation. http:\/\/gis.iu.edu\/datasetInfo\/statewide\/in_2011.php."},{"key":"e_1_2_1_15_1","first-page":"1593","article-title":"Extracting topographic structure from digital elevation data for geographic information system analysis","volume":"54","author":"Jenson S. K.","year":"1988","journal-title":"Photogrammetric Engineering and Remote Sensing"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.269238"},{"key":"e_1_2_1_17_1","volume-title":"Flood Risk Management: Research and Practice","author":"Lhomme Julien"},{"key":"e_1_2_1_18_1","volume-title":"Proc. 11th Intl. Sympos. on Spatial Data Handling. Springer","author":"Liu Y."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274895.3274980"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0734-189X(84)80011-0"},{"key":"e_1_2_1_21_1","unstructured":"Pennsylvania Spatial Data Access. 2008. PAMAP Program DEM Mosaics by Lidar Delivery Zones. http:\/\/www.pasda.psu.edu\/uci\/SearchResults.aspx?Keyword=PAMAP. Pennsylvania Spatial Data Access. 2008. PAMAP Program DEM Mosaics by Lidar Delivery Zones. http:\/\/www.pasda.psu.edu\/uci\/SearchResults.aspx?Keyword=PAMAP."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/hyp.3360050106"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3139985"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276892"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.catena.2014.10.017"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/wrcr.20324"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340707","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340707","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3340707","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:11Z","timestamp":1750200071000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3340707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,18]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3340707"],"URL":"https:\/\/doi.org\/10.1145\/3340707","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"value":"2374-0353","type":"print"},{"value":"2374-0361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,18]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}