2007.12.17 | Lars Allan Arge

I/O Efficient Algorithms for
Batched Union-Find with Dynamic Set Properties
and its Applications to Hydrological Conditioning

In this thesis we expand the definition of topological persistence to include topological volume persistence and topological area persistence. We show that both topological persistence measures in theory can be computed using O(sort(N)) on both grid and TIN DEMs and provide an O(sort(N) log N/M) algorithm that is practically efficient.

To solve the problem of computing topological volume persistence and topological area persistence we define the batched union-find with dynamic set properties problem. We solve this problem by expanding the previous batched union-find results to describe both a O(sort(N)) graph theoretic solution, a O(sort(N)) geometric solution and a practically efficient O(sort(N) log N/M) solution.

Finally,we describe an implementation of the practically efficientalgorithm that computes both topological area persistence and topological volume persistence. The implementation is integrated with the TerraSTREAM software package. We use thewater flow modelling and contour line computation modules of TerraSTREAM to illustrate, how hydrological conditioning using topological volume persistence improves the output of both water flow modelling and contour line generation.