Module min_plus_convolution 

Exact min-plus convolution algorithms for structured integer sequences.

T::maximum() represents positive infinity. Callers must choose a signed integer type that can represent every finite result and every intermediate arithmetic expression used by the selected algorithm.

Re-exports

pub use self::concave::min_plus_convolution_concave_both;

pub use self::concave::min_plus_convolution_concave_envelope;

pub use self::convex::min_plus_convolution_convex_divide_and_conquer;

pub use self::convex::min_plus_convolution_convex_merge;

pub use self::convex::min_plus_convolution_convex_smawk;

pub use self::monotone::min_plus_convolution_monotone_runs;

pub use self::near_convex::min_plus_convolution_near_convex_scan;

pub use self::piecewise_linear::min_plus_convolution_linear;

pub use self::piecewise_linear::min_plus_convolution_piecewise_linear;

pub use self::selector::min_plus_convolution;

pub use self::squared_distance::min_plus_convolution_with_squared_distance;

Modules

concave 🔒

convex 🔒

monotone 🔒

near_convex 🔒

piecewise_linear 🔒

selector 🔒

squared_distance 🔒

Structs

BoundedRequirements 🔒

Constants

MAX_NTT_SIZE 🔒

Functions

assert_finite 🔒

bounded_requirements_from_extrema 🔒

bounded_transform_len 🔒

finite_extrema 🔒

min_plus_convolution_bounded_ntt

Computes exact min-plus convolution for small integer value spans using NTT.

min_plus_convolution_naive

Computes min-plus convolution by enumerating all input pairs.

min_plus_convolution_sparse

Computes min-plus convolution by enumerating finite input pairs only.

output_len 🔒

sparse 🔒