Asymptotically Optimal Algorithms for Running Max and Min Filters on Random Inputs.

Given a d-dimensional array of size ndand an integer p, the running max (or min) filter is the set of maximum (or minimum) elements within a d-dimensional sliding window of edge length p inside the array. This problem is useful in many signal processing applications such as pattern analysis, adaptive signal processing, and morphological analysis. The current best algorithm for computing the one-di...