# Efficient Second-Order Shape-Constrained Function Fitting

Aug 2019 (Written: Feb 2019)

David Durfee, Yu Gao, Anup B. Rao, and Sebastian Wild:

Algorithms and Data Structures Symposium (WADS) 2019
in Z. Friggstad, JR. Sack, M. Salavatipour (Eds.): WADS 2019, LNCS 11646, Springer, 2019, pp 395–408

This paper describes a novel dynamic-programming algorithm for testing whether a given set of points $(x_1,y_1),\ldots,(x_n,y_n)$ can be explained by a (discrete) function that must satisfy bounds on its (discrete) first- and second-order derivatives.
The DP algorithm can thus find, e.g., a convex regression function with $L_\infty$ error at most OPT + ε in time $O(n \log (U/\varepsilon))$, where $U$ captures the universe size of numbers in the input.