Function smawk::column_minima

pub fn 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 efficiently 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).

Examples

use smawk::Matrix;
let matrix = vec![vec![4, 2, 4, 3],
                  vec![5, 3, 5, 3],
                  vec![5, 3, 3, 1]];
assert_eq!(smawk::column_minima(&matrix),
           vec![0, 0, 2, 2]);

Panics

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