Alluvial Connectivity in Multi-Channel Networks in Rivers and Estuaries
Willem Sonke, Maarten G. Kleinhans, Bettina Speckmann, Wout M. van Dijk, and Matthew Hiatt.
Earth Surface Processes and Landforms,
47(2):477—490,
2022.
－ Abstract
<p>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.</p>
－ BibTeX
@article{alluvial-connectivity-in-multi-channel-networks-in-rivers-and-estuaries:2022,
title = {Alluvial Connectivity in Multi-Channel Networks in Rivers and Estuaries},
author = {Willem Sonke and Maarten G. Kleinhans and Bettina Speckmann and Wout M. van Dijk and Matthew Hiatt},
year = {2022},
bookTitle = {Earth Surface Processes and Landforms},
}
[ PDF ]
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares
Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms.
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022),
pp. 4:1—4:19,
2022.
－ Abstract
<p>Edge-connected configurations of square modules, which can reconfigure through so-called sliding moves, are a well-established theoretical model for modular robots in two dimensions. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one edge-connected configuration of n squares into any other using at most O(n2) sliding moves, while keeping the configuration connected at all times. For certain pairs of configurations, reconfiguration may require ω(n2) sliding moves. However, significantly fewer moves may be sufficient. We prove that it is NP-hard to minimize the number of sliding moves for a given pair of edge-connected configurations. On the positive side we present Gather&Compact, an input-sensitive in-place algorithm that requires only O( Pn) sliding moves to transform one configuration into the other, where P is the maximum perimeter of the two bounding boxes. The squares move within the bounding boxes only, with the exception of at most one square at a time which may move through the positions adjacent to the bounding boxes. The O( Pn) bound never exceeds O(n2), and is optimal (up to constant factors) among all bounds parameterized by just n and P. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally arrive at a single solid xy-monotone component. We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin, on all types of square configurations.</p>
－ BibTeX
@article{compacting-squares-input-sensitive-in-place-reconfiguration-of-sliding-squares:2022,
title = {Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares},
author = {Hugo A. Akitaya and Erik D. Demaine and Matias Korman and Irina Kostitsyna and Irene Parada and Willem Sonke and Bettina Speckmann and Ryuhei Uehara and Jules Wulms},
year = {2022},
bookTitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
}
