Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/13873

Flow computations on imprecise terrains
Driemel, Anne; Haverkort, Herman; Löffler, Maarten; Silveira, Rodrigo Ignacio
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
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
À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
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
Springer Verlag
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Driemel, Anne; Haverkort, Herman; Löffler, Maarten; Silveira, Rodrigo Ignacio
Agarwal, Pankaj; Aronov, Boris; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio
Buchin, Kevin; Kostitsyna, Irina; Löffler, Maarten; Silveira, Rodrigo Ignacio
Löffler, Maarten; Saumell, Maria; Silveira, Rodrigo Ignacio
Buchin, Kevin; Buchin, Maike; Kreveld, Marc van; Löffler, Maarten; Silveira, Rodrigo Ignacio; Wenk, Carola; Wiratma, Lionov