Efficient algorithms for finding sills in digital topographic maps

In stratified geophysical flows, the energetically optimal exchange of dense fluid across a topographic barrier generally takes place at the deepest unblocked connection, which is typically a saddle point (sill). The flow at or near a sill is often hydraulically controlled, in which case the sill is called a controlling sill. Oceanographic examples include overflows of newly formed dense water at high latitudes as well as sills in channels connecting major ocean basins, such as the Strait of Gibraltar. Controlling sills are usually associated with strong flows, making them ideal sites for monitoring transport and hydrographic variability. The locations and depths of controlling sills also provide strong constraints for the downstream hydrographic properties below sill depth. Here, two algorithms for finding sills in digital topographic maps are presented. The first approximates the sill height to arbitrary precision in O(k)O(k) steps, where k   is the number of data points in the map. The second algorithm, which requires O(klogk)O(klogk) steps, additionally returns the sill location. Several tests carried out with realistic problems from physical oceanography reveal that the second algorithm runs faster in practice, even though its worst case behavior is worse.