publication . Contribution for newspaper or weekly magazine . Conference object . 2010

I/O-efficient computation of water flow across a terrain

Lars Arge; Morten Revsbaek; Norbert Zeh;
Restricted English
  • Published: 01 Jan 2010
  • Publisher: Association for Computing Machinery
Abstract
Consider rain falling at a uniform rate onto a terrain <em>T</em> represented as a triangular irregular network. Over time, water collects in the basins of <em>T</em>, forming lakes that spill into adjacent basins. Our goal is to compute, for each terrain vertex, the time this vertex is flooded (covered by water). We present an I/O-efficient algorithm that solves this problem using <em>O</em>(sort(<em>X</em>) log (<em>X</em>/<em>M</em>) + sort(<em>N</em>)) I/Os, where <em>N</em> is the number of terrain vertices, <em>X</em> is the number of pits of the terrain, sort(<em>N</em>) is the cost of sorting <em>N</em> data items, and <em>M</em> is the size of the compu...
Subjects
ACM Computing Classification System: ComputingMethodologies_COMPUTERGRAPHICSComputerApplications_COMPUTERSINOTHERSYSTEMS
free text keywords: Vertex (geometry), Combinatorics, Triangulated irregular network, Terrain, Input/output, Discrete mathematics, Sorting, Water flow, Computation, sort, Computer science
Related Organizations
Download fromView all 2 versions
PURE Aarhus University
Contribution for newspaper or weekly magazine . 2010
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Contribution for newspaper or weekly magazine . Conference object . 2010

I/O-efficient computation of water flow across a terrain

Lars Arge; Morten Revsbaek; Norbert Zeh;