Flow Computations on Imprecise Terrains

DOI10.1007/978-3-642-22300-6_30zbMATH Open1342.68333arXiv1111.1651OpenAlexW2170704164MaRDI QIDQ5199256FDOQ5199256

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)

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.

Full work available at URL: https://arxiv.org/abs/1111.1651

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

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)

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)