Search

Channels in rivers and estuaries are the main paths of fluvial and tidal currents that transport sediment through the system. While network representations of multi-channel systems and their connectivity are quite useful for characterisation of braiding patterns and dynamics, the recognition of channels and their properties is complicated because of the large bed elevation variations, such as shallow shoals and bed steps that render channels visually disconnected. We present and analyse two mathematically rigorous methods to identify channel networks from a terrain model of the river bed. Both methods construct a dense network of locally steepest-descent channels from saddle points on the terrain, and select a subset of channels with a certain minimum sediment volume between them. This is closely linked to the main mechanism of channel formation and change by displacement of sediment volume. The two methods differ in how they compute these sediment volumes: either globally through the entire length of the river, or locally. We compare the methods for the measured bathymetry of the Western Scheldt estuary, The Netherlands, over the past decades. The global method is overly sensitive to small changes elsewhere in the network compared to the local method. We conclude that the local method works best conceptually and for stability reasons. The associated concept of alluvial connectivity between channels in a network is thus the inverse of the volume of sediment that must be displaced to merge the channels. Our method opens up possibilities for new analyses as shown in two examples. First, it shows a clear pattern of scale dependence on volume of the total network length and of the number of nodes by a power law relation, showing that the smaller channels are relatively much shorter. Second, channel bifurcations were found to be predominantly mildly asymmetrical, which is unexpected from fluvial bifurcation theory.

We describe SquareSlider, a software framework for visualizing reconfiguration algorithms of modular robots in the sliding square model. In this model, a robot consists of a configuration of squares in a rectangular grid, which can reconfigure through a fixed set of possible moves. SquareSlider is a web-based tool that implements an easy-to-use interface allowing the user to build a configuration, run a reconfiguration algorithm on it, and examine the results.

We describe SquareSlider, a software framework for visualizing reconfiguration algorithms of modular robots in the sliding square model. In this model, a robot consists of a configuration of squares in a rectangular grid, which can reconfigure through a fixed set of possible moves. SquareSlider is a web-based tool that implements an easy-to-use interface allowing the user to build a configuration, run a reconfiguration algorithm on it, and examine the results.

Shipping fairways in estuaries are continuously dredged to maintain access for large vessels to major ports. However, several estuaries worldwide show adverse side effects to dredging activities, in particular affecting morphology and ecologically valuable habitats. We used physical scale experiments, field assessments of the Western Scheldt estuary (the Netherlands), and morphodynamic model runs to analyse the effects of dredging and future stresses (climate and sediment management) on a multi-channel system and its ecologically valuable intertidal flats. All methods indicate that dredging and disposal strategies are unfavourable to long-term morphology because dredging creates and propagates the imbalance between shallow and deeper parts of the estuary, causing a loss of valuable connecting channels and fixation of the tidal flats and main channel positions, while countering adverse effects by disposal strategy has limited effectiveness. Changing the disposal strategy towards main channel scour disposal can be economically and ecologically beneficial for the preservation of the multi-channel system. Further channel deepening will accelerate the adverse side effects, whereas future sea-level rise may revive the multi-channel system.

Given two shapes A and B in the plane with Hausdorff distance 1, is there a shape S with Hausdorff distance 1/2 to and from A and B? The answer is always yes, and depending on convexity of A and/or B, S may be convex, connected, or disconnected. We show a generalization of this result on Hausdorff distances and middle shapes, and show some related properties. We also show that a generalization of such middle shapes implies a morph with a bounded rate of change. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two sets and show how to approximate or compute it.

Outlines (closed loops) delineate areas of interest on terrains, such as regions with a heightened risk of landslides. For various analysis tasks it is necessary to define and compute a volume of earth (soil) based on such an outline, capturing, for example, the possible volume of a landslide in a high-risk region. In this paper we discuss several options to define meaningful 2D surfaces induced by a 1D outline, which allow us to compute such volumes. We experimentally compare the proposed surface options for two applications: similarity of paths on terrains and landslide susceptibility analysis.

Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are δ-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum δ-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.

Persistence is the method of choice to simplify terrains by removing insignificant features while retaining topologically important ones. Motivated by applications in geomorphology, we study volume-persistence, a variant of persistence which is based on the volume underneath the terrain (instead of the usual vertex heights). Specifically, we want to kinetically maintain a volume-simplified time-varying terrain. In this paper we describe a kinetic data structure (KDS) that maintains the pruned split tree of an area-persistent 1D terrain under linear vertex motion. The main ingredient of this KDS is an algorithm that detects those combinatorial events when a pruned part of the terrain attains a certain threshold volume.

The Morse-Smale complex of a terrain is a topological complex that provides information about the features of the terrain. It consists of the critical points (minima, saddles and maxima), together with steepest-descent paths from saddles to minima and steepest-ascent paths from saddles to maxima. We describe a kinetic data structure to maintain the Morse-Smale-complex for a triangulated terrain whose vertex heights change continuously. This can be used to efficiently analyze time-varying data.

Linear layouts are a simple and natural way to draw a graph: all vertices are placed on a single line and edges are drawn as arcs between the vertices. Despite its simplicity, a linear layout can be a very meaningful visualization if there is a particular order defined on the vertices. Common examples of such ordered - and often also directed - graphs are event sequences and processes: public transport systems tracking passenger check-in and check-out, banks checking online transactions, or hospitals recording the paths of patients through their system, to name a few. A main drawback of linear layouts are the usually (very) large aspect ratios of the resulting drawings, which prevent users from obtaining a good overview of the whole graph. In this paper we present a novel and versatile algorithm to optimally fold a linear layout of a graph such that it can be drawn effectively in a specified aspect ratio, while still clearly communicating the linearity of the layout.

Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are delta-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum delta-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.

Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are delta-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum delta-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.

Ruler of the Plane is a set of games illustrating concepts from combinatorial and computational geometry. The games are based on the art gallery problem, ham-sandwich cuts, the Voronoi game, and geometric network connectivity problems like the Euclidean minimum spanning tree and traveling salesperson problem.

We show how to represent a simple polygon P by a (pixel-based) grid polygon Q that is simple and whose Hausdorff or Fréchet distance to P is small. For any simple polygon P, a grid polygon exists with constant Hausdorff distance between their boundaries and their interiors. Moreover, we show that with a realistic input assumption we can also realize constant Fréchet distance between the boundaries. We present algorithms accompanying these constructions, heuristics to improve their output while keeping the distance bounds, and experiments to assess the output.