|| Checking for direct PDF access through Ovid
A new algorithm to compute the Legendre–Fenchel transform is proposed and investigated. The so-called Linear-time Legendre Transform (LLT) improves all previously known Fast Legendre Transform algorithms by reducing their log-linear worst-case time complexity to linear. Since the algorithm amounts to computing several convex hulls and sorting, any convex hull algorithm well-suited for a particular problem gives a corresponding LLT algorithm. After justifying the convergence of the Discrete Legendre Transform to the Legendre–Fenchel transform, an extended computation time complexity analysis is given and confirmed by numerical tests. Finally, the LLT is illustrated with several examples and a LLT MATLAB package is described.