Struct PiecewiseLinearConvexFn

pub struct PiecewiseLinearConvexFn { /* private fields */ }

Represents a maximum (upper envelope) of a collection of linear functions of one variable, evaluated using an online version of the convex hull trick. It combines the offline algorithm with square root decomposition, resulting in an asymptotically suboptimal but simple algorithm with good amortized performance: N inserts interleaved with Q queries yields O(N sqrt Q + Q log N) time complexity in general, or O((N + Q) log N) if all queries come after all inserts.

Implementations

impl PiecewiseLinearConvexFn

pub fn max_with(&mut self, new_m: f64, new_b: f64)

Replaces the represented function with the maximum of itself and a provided line

pub fn evaluate(&mut self, x: f64) -> f64

Evaluates the function at x with good amortized runtime

Trait Implementations

impl Default for PiecewiseLinearConvexFn

fn default() -> PiecewiseLinearConvexFn

Returns the “default value” for a type.