The computational geometry of hydrology data in geographic information systems

Computational geometry counts geographic information systems (GIS) among its application areas. GIS data sets are large and are related to the Earth's surface by geometric coordinates. These properties mesh with geometry algorithms and their asymptotic analyses. This dissertation investigates the geometry in a specialized set of GIS problems, namely finding river network centrelines and finding watershed boundaries. Our goal is to create robust and consistent algorithms that solve these problems efficiently.; When finding river network centrelines, the main issue is the robustness of the algorithm. The medial axis is an excellent centreline for a river or lake, but few robust implementations exist. Moreover, the medial axis uses parabolic segments, which are harder to represent accurately than line segments. We approximate the medial axis with a piecewise-linear structure that we compute with a robust algorithm for point Voronoi diagrams. Our approximation provides estimates of river area and associates the points on the centreline with the nearest river bank points, much like the medial axis. In turn, we use this association to identify opposite points along river banks.; When finding watershed boundaries on triangulated terrains, we focus on finding an algorithm that is consistent with the terrain. In previous work, Nelson et al. [66] locate regions that drain to a common location, but their solution can be disconnected in degenerate cases. We propose a vector algorithm whose watersheds are consistent with the assumption on how water flows on the terrain: the algorithm guarantees one polygon per watershed. Our algorithm finds the watershed boundaries for local minima in the terrain in O(n log n + k) worst-case time where n is the number of points that model the terrain and k is the complexity of the watershed boundaries.; We apply our solutions for these GIS problems to data in the British Columbia TRIM (Terrain Resource Inventory Mapping) format. For river networks, we find centrelines for the Fraser River in British Columbia and for a subset of its tributaries. We link these centrelines into a single river network. We have used this network to model the migration of salmon. For watersheds, we identify the boundaries of watersheds in the mountains north of Vancouver, British Columbia and compare the boundaries with manually-digitized watersheds of the same region.