# Crate gcm_lcm

Expand description

## 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

• The result of greatest convex minorant construction, which occurs via `gcm` or `gcm_unordered`.
• The result of least concave majorant construction, which occurs via `lcm` or `lcm_unordered`.

## Functions

• 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.
• 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.
• 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.
• 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.