Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user1D and 2D Flow Routing on a Terrain
100
0
0.0
(
0
)
Added by
Aaron Lowe
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Aaron Lowe
Ask ChatGPT about the research
No Arabic abstract
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 $Sigma$, 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 $Sigma$ 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 $Sigma$ in $O(rho k+|phi| log n)$ time, where $rho$ is the number of sinks in $Sigma$, $k$ is the number of times the rain distribution changes, and $|phi|$ 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 $Sigma$ 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}(|phi|))$ I/Os and $O(|phi| log |phi|)$ internal computation time. (iii) $Sigma$ 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 Sigma$ 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 Mannings 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.
rate research
Read More
We consider the problem of routing on a network in the presence of line segment constraints (i.e., obstacles that edges in our network are not allowed to cross). Let $P$ be a set of $n$ points in the plane and let $S$ be a set of non-crossing line segments whose endpoints are in $P$. We present two deterministic 1-local $O(1)$-memory routing algorithms that are guaranteed to find a path of at most linear size between any pair of vertices of the emph{visibility graph} of $P$ with respect to a set of constraints $S$ (i.e., the algorithms never look beyond the direct neighbours of the current location and store only a constant amount of additional information). Contrary to {em all} existing deterministic local routing algorithms, our routing algorithms do not route on a plane subgraph of the visibility graph. Additionally, we provide lower bounds on the routing ratio of any deterministic local routing algorithm on the visibility graph.
We study the problem of visibility in polyhedral terrains in the presence of multiple viewpoints. We consider a triangulated terrain with $m>1$ viewpoints (or guards) located on the terrain surface. A point on the terrain is considered emph{visible} if it has an unobstructed line of sight to at least one viewpoint. We study several natural and fundamental visibility structures: (1) the visibility map, which is a partition of the terrain into visible and invisible regions; (2) the emph{colored} visibility map, which is a partition of the terrain into regions whose points have exactly the same visible viewpoints; and (3) the Voronoi visibility map, which is a partition of the terrain into regions whose points have the same closest visible viewpoint. We study the complexity of each structure for both 1.5D and 2.5D terrains, and provide efficient algorithms to construct them. Our algorithm for the visibility map in 2.5D terrains improves on the only existing algorithm in this setting. To the best of our knowledge, the other structures have not been studied before.
A terrain is an $x$-monotone polygon whose lower boundary is a single line segment. We present an algorithm to find in a terrain a triangle of largest area in $O(n log n)$ time, where $n$ is the number of vertices defining the terrain. The best previous algorithm for this problem has a running time of $O(n^2)$.
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.
An important task when working with terrain models is computing viewsheds: the parts of the terrain visible from a given viewpoint. When the terrain is modeled as a polyhedral terrain, the viewshed is composed of the union of all the triangle parts that are visible from the viewpoint. The complexity of a viewshed can vary significantly, from constant to quadratic in the number of terrain vertices, depending on the terrain topography and the viewpoint position. In this work we study a new topographic attribute, the emph{prickliness}, that measures the number of local maxima in a terrain from all possible perspectives. We show that the prickliness effectively captures the potential of 2.5D terrains to have high complexity viewsheds, and we present near-optimal algorithms to compute the prickliness of 1.5D and 2.5D terrains. We also report on some experiments relating the prickliness of real word 2.5D terrains to the size of the terrains and to their viewshed complexity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
