Function smawk::smawk_row_minima

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

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

This implements the SMAWK algorithm for finding row 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 columns.