{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T06:39:04Z","timestamp":1756190344948,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T00:00:00Z","timestamp":1553990400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Danish National Research Foundation and Innovation Fund Denmark"},{"name":"ARO","award":["W911NF-15-1-0408, and 2012\/229"],"award-info":[{"award-number":["W911NF-15-1-0408, and 2012\/229"]}]},{"name":"U.S.-Israel Binational Science Foundation"},{"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,3,31]]},"abstract":"<jats:p>\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 the\n            <jats:italic>flooding query<\/jats:italic>\n            problem: Preprocess a given terrain \u03a3, represented as a triangulated\n            <jats:italic>xy<\/jats:italic>\n            -monotone surface with\n            <jats:italic>n<\/jats:italic>\n            vertices, into a data structure so that for a query rain region\n            <jats:italic>R<\/jats:italic>\n            and a query point\n            <jats:italic>q<\/jats:italic>\n            on \u03a3, one can quickly determine how much rain has to fall in\n            <jats:italic>R<\/jats:italic>\n            so that\n            <jats:italic>q<\/jats:italic>\n            is flooded. Available terrain data is often subject to uncertainty, which must be incorporated into the terrain analysis. For instance, the digital elevation models of terrains have to be refined to incorporate underground pipes, tunnels, and waterways under bridges, but there is often uncertainty in their existence. By representing the uncertainty in the terrain data explicitly, we can develop methods for flood risk analysis that properly incorporate terrain uncertainty when reporting what areas are at risk of flooding.\n          <\/jats:p>\n          <jats:p>\n            We present two results. First, we present an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )-time algorithm for preprocessing \u03a3 with a linear-size data structure that can answer a flooding query in\n            <jats:italic>O<\/jats:italic>\n            (|\n            <jats:italic>R<\/jats:italic>\n            | +\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time, where |\n            <jats:italic>R<\/jats:italic>\n            | is the number of vertices in\n            <jats:italic>R<\/jats:italic>\n            ,\n            <jats:italic>m<\/jats:italic>\n            is the number of so-called tributaries of\n            <jats:italic>q<\/jats:italic>\n            at which rain is falling, and\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices of the terrain. Next, we extend this data structure to handle \u201cuncertain\u201d terrains using a standard Monte Carlo method. Given a probability distribution on terrain data, our data structure returns the probability of a query point being flooded if a specified amount of rain falls on a query region. We implement our data structure and test it on real terrains, showing that a small number of samples suffice to accurately estimate the flood risk.\n          <\/jats:p>","DOI":"10.1145\/3295459","type":"journal-article","created":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T12:28:42Z","timestamp":1559824122000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Flood Risk Analysis on Terrains"],"prefix":"10.1145","volume":"5","author":[{"given":"Mathias","family":"Rav","sequence":"first","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aaron","family":"Lowe","sequence":"additional","affiliation":[{"name":"Duke University, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj K.","family":"Agarwal","sequence":"additional","affiliation":[{"name":"Duke University, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868249"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820823"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025526421410"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974768.21"},{"key":"e_1_2_1_5_1","unstructured":"Lars Arge Mathias Rav Morten Revsb\u00e6k Yujin Shin and Jungwoo Yang. Manuscript. Sea-rise flood prediction on massive dynamic terrains.  Lars Arge Mathias Rav Morten Revsb\u00e6k Yujin Shin and Jungwoo Yang. Manuscript. Sea-rise flood prediction on massive dynamic terrains."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_116"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1810959.1811026"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.7146\/brics.v1i35.21608"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214082"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00093-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.009"},{"key":"e_1_2_1_13_1","unstructured":"Danish Geodata Agency. 2007. The Danish Elevation Model DHM-2007\/Terr\u00e6n_bro. Retrieved from http:\/\/eng.gst.dk.  Danish Geodata Agency. 2007. The Danish Elevation Model DHM-2007\/Terr\u00e6n_bro. Retrieved from http:\/\/eng.gst.dk."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341012.1341049"},{"key":"e_1_2_1_15_1","first-page":"1","article-title":"Hierarchical Morse\u2014Smale complexes for piecewise linear 2-manifolds","volume":"30","year":"2003","journal-title":"Discrete Comput. Geom."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1975.11976431"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/173","volume-title":"Geometric Approximation Algorithms","author":"Har-Peled Sariel","year":"2011"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2189-8","volume-title":"Algebraic Geometry: A First Course","author":"Harris Joe","year":"1992"},{"key":"e_1_2_1_20_1","unstructured":"Indiana Spatial Data Portal. 2013. Indiana Orthophotography (RGBI) LiDAR and Elevation. Retrieved from http:\/\/gis.iu.edu\/datasetInfo\/statewide\/in_2011.php.  Indiana Spatial Data Portal. 2013. Indiana Orthophotography (RGBI) LiDAR and Elevation. Retrieved from http:\/\/gis.iu.edu\/datasetInfo\/statewide\/in_2011.php."},{"key":"e_1_2_1_21_1","first-page":"1593","article-title":"Extracting topographic structure from digital elevation data for geographic information system analysis","volume":"54","author":"Jenson Susan K.","year":"1988","journal-title":"Photogramm. Eng. Remote Sens."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/262839.269238"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-26772-7_11"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274895.3274980"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0734-189X(84)80011-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3139985"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276892"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3295459","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3295459","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3295459","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:13Z","timestamp":1750208533000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3295459"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,31]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3295459"],"URL":"https:\/\/doi.org\/10.1145\/3295459","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2019,3,31]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}