Crate gcm_lcm

gcm-lcm

Construction of either the greatest convex minorant or least concave majorant. Guaranteed O(n) time complexity for ordered input, or O(n * logn) worst-case time complexity for unordered inputs. The resultant function approximation can then be used to compute points via interpolation, or, alternatively, if the first derivative is of the function is of interest, the derivative method provides self-consistent values without which avoid error incurred by finite difference.

Structs

Gcm

The result of greatest convex minorant construction, which occurs via gcm or gcm_unordered.

Lcm

The result of least concave majorant construction, which occurs via lcm or lcm_unordered.

Functions

gcm

Construct the greatest convex minorant of the sequence of points (xᵢ, yᵢ), i = 0,…,n-1, assuming that (1) the values satisfy xᵢ < xᵢ₊₁ for i = 0,…,n-2, (2) -∞ < xᵢ < ∞ ∀i, and (3) xᵢ is not NaN ∀i. The result of the algorithm is essentially meaningless if these three conditions are not satisfied; however, the implementation will not panic. In addition to the three conditions above, n must be at least 2, and x.len() == y.len() must hold. Failure to satisfy these two conditions will result in a panic.

gcm_unordered

Construct the greatest convex minorant of the sequence of points, (xᵢ, yᵢ), i = 0,…,n-1, assuming that (1) -∞ < xᵢ < ∞ ∀i, and (2) xᵢ is not NaN ∀i. In contrast to gcm, it is not assumed that x is ordered such that xᵢ < xᵢ₊₁, nor that the elements of x are unique. Points in the ordered sequence for which xᵢ = xᵢ₊₁ will be de-duplicated by pairing the unique x-value with the minimum of the respective y-values. In addition to the conditions above, x.len() == y.len() must hold and the number of unique points (after applying the de-duplication above) must be at least 2.

lcm

Construct the least concave majorant of the sequence of points (xᵢ, yᵢ), i = 0,…,n-1, assuming that (1) the values satisfy xᵢ < xᵢ₊₁ for i = 0,…,n-2, (2) -∞ < xᵢ < ∞ ∀i, and (3) xᵢ is not NaN ∀i. The result of the algorithm is essentially meaningless if these three conditions are not satisfied; however, the implementation will not panic. In addition to the three conditions above, n must be at least 2, and x.len() == y.len() must hold. Failure to satisfy these two conditions will result in a panic.

lcm_unordered

Construct the least concave majorant of the sequence of points, (xᵢ, yᵢ), i = 0,…,n-1, assuming that (1) -∞ < xᵢ < ∞ ∀i, and (2) xᵢ is not NaN ∀i. In contrast to lcm, it is not assumed that x is ordered such that xᵢ < xᵢ₊₁, nor that the elements of x are unique. Points in the ordered sequence for which xᵢ = xᵢ₊₁ will be de-duplicated by pairing the unique x-value with the maximum of the respective y-values. In addition to the conditions above, x.len() == y.len() must hold and the number of unique points (after applying the de-duplication above) must be at least 2.