Flow Computations on Imprecise Terrains

DOI10.1007/978-3-642-22300-6_30MaRDI QIDQ5199256zbMATH OpenOpenAlexFDO

Authors Anne Driemel, Maarten Löffler, Rodrigo I. Silveira, Herman Haverkort

Publication date 12 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1651, http://hdl.handle.net/2117/20799

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We study the computation of the flow of water 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.

Recommendations

• Flow computations on imprecise terrains
• The complexity of flow on fat terrains and its i/o-efficient computation
• Flow over complex terrain estimated by a general purpose Navier-Stokes solver
• Energy-bounded flow approximation on a Cartesian-product grid over rough terrain
• I/O-efficient computation of water flow across a terrain
• Implicit flow routing on terrains with applications to surface networks and drainage structures
• On the improved finite volume procedure for simulation of turbulent flows over real complex terrains
• I/O-Efficient Flow Modeling on Fat Terrains
• scientific article; zbMATH DE number 1302262

Cited in

(7)

• Energy-bounded flow approximation on a Cartesian-product grid over rough terrain
• Implicit flow routing on terrains with applications to surface networks and drainage structures
• Flow computations on imprecise terrains
• I/O-Efficient Flow Modeling on Fat Terrains
• Flow over complex terrain estimated by a general purpose Navier-Stokes solver
• The complexity of flow on fat terrains and its i/o-efficient computation
• Smoothing Imprecise 1.5D Terrains

This page was built for publication: Flow Computations on Imprecise Terrains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199256)