2026-04-13T02:13:41Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/138732026-01-14T08:09:25Zcom_2072_1033col_2072_452950

urn:hdl:2117/13873 Flow computations on imprecise terrains Driemel, Anne Haverkort, Herman Löffler, Maarten Silveira, Rodrigo Ignacio Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències Operations research Management science Geophysics Optimització i investigació operativa Física matemàtica 90B Operations research and management science 86 GEOPHYSICS We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predefined graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x, y)-coordinates are fixed. For the first model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time. Peer Reviewed Postprint (published version) 2011 Conference report http://cataleg.upc.edu/record=b1390385~S1*cat info:eu-repo/grantAgreement/EC/FP7/251235/EU/Mathematical Foundations of High-Quality Terrain Models/MFHQTERRAINS http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Restricted access - confidentiality agreement Attribution-NonCommercial-NoDerivs 3.0 Spain Springer Verlag