Function smawk::smawk_column_minima

pub fn smawk_column_minima<T: PartialOrd + Copy, M: Matrix<T>>(
    matrix: &M
) -> Vec<usize>

Compute column minima in O(m + n) time.

This implements the SMAWK algorithm for finding column minima in a totally monotone matrix.

The SMAWK algorithm is from Agarwal, Klawe, Moran, Shor, and Wilbur, Geometric applications of a matrix searching algorithm, Algorithmica 2, pp. 195-208 (1987) and the code here is a translation David Eppstein's Python code.

Running time on an m ✕ n matrix: O(m + n).

Panics

It is an error to call this on a matrix with zero rows.