Source author record

Lars Arge

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

1D and 2D Flow Routing on a Terrain

An important problem in terrain analysis is modeling how water flows across a terrain creating floods by forming channels and filling depressions. In this paper we study a number of \emph{flow-query} related problems: Given a terrain $Σ$ , represented as a triangulated $xy$ -monotone surface with $n$ vertices, a rain distribution $R$ which may vary over time, determine how much water is flowing over a given edge as a function of time. We develop internal-memory as well as I/O-efficient algorithms for flow queries. This paper contains four main results: (i) We present an internal-memory algorithm that preprocesses $Σ$ into a linear-size data structure that for a (possibly time varying) rain distribution $R$ can return the flow-rate functions of all edges of $Σ$ in $O(ρk+|ϕ| \log n)$ time, where $ρ$ is the number of sinks in $Σ$ , $k$ is the number of times the rain distribution changes, and $|ϕ|$ is the total complexity of the flow-rate functions that have non-zero values; (ii) We also present an I/O-efficient algorithm for preprocessing $Σ$ into a linear-size data structure so that for a rain distribution $R$ , it can compute the flow-rate function of all edges using $O(\text{Sort}(|ϕ|))$ I/Os and $O(|ϕ| \log |ϕ|)$ internal computation time. (iii) $Σ$ can be preprocessed into a linear-size data structure so that for a given rain distribution $R$ , the flow-rate function of an edge $(q,r) \in Σ$ under the single-flow direction (SFD) model can be computed more efficiently. (iv) We present an algorithm for computing the two-dimensional channel along which water flows using Manning's equation; a widely used empirical equation that relates the flow-rate of water in an open channel to the geometry of the channel along with the height of water in the channel.

preprint2014arXiv

Maintaining Contour Trees of Dynamic Terrains

We consider maintaining the contour tree $\mathbb{T}$ of a piecewise-linear triangulation $\mathbb{M}$ that is the graph of a time varying height function $h: \mathbb{R}^2 \rightarrow \mathbb{R}$ . We carefully describe the combinatorial change in $\mathbb{T}$ that happen as $h$ varies over time and how these changes relate to topological changes in $\mathbb{M}$ . We present a kinetic data structure that maintains the contour tree of $h$ over time. Our data structure maintains certificates that fail only when $h(v)=h(u)$ for two adjacent vertices $v$ and $u$ in $\mathbb{M}$ , or when two saddle vertices lie on the same contour of $\mathbb{M}$ . A certificate failure is handled in $O(\log(n))$ time. We also show how our data structure can be extended to handle a set of general update operations on $\mathbb{M}$ and how it can be applied to maintain topological persistence pairs of time varying functions.

preprint2013arXiv

RAM-Efficient External Memory Sorting

In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we study algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.