Czechoslovak Mathematical Journal, first online, pp. 1-23

A new algorithm for approximating the least concave majorant

Martin Franců, Ron Kerman, Gord Sinnamon

Received August 1, 2016.   First published August 16, 2017

Abstract:  The least concave majorant, $\hat F$, of a continuous function $F$ on a closed interval, $I$, is defined by
\hat F (x) = \inf\{ G(x) G \geq F, G \text{ concave}\},\quad x \in I.
We present an algorithm, in the spirit of the Jarvis March, to approximate the least concave majorant of a differentiable piecewise polynomial function of degree at most three on $I$. Given any function $F \in\mathcal{C}^4(I)$, it can be well-approximated on $I$ by a clamped cubic spline $S$. We show that $\hat S$ is then a good approximation to $\hat F$. We give two examples, one to illustrate, the other to apply our algorithm.
Keywords:  least concave majorant; level function; spline approximation
Classification MSC:  26A51, 52A41, 46N10
DOI:  10.21136/CMJ.2017.0408-16

PDF available at:  Springer   Institute of Mathematics CAS

[1] Y. A. Brudnyĭ, N. Y. Krugljak: Interpolation Functors and Interpolation Spaces. Vol. 1. North-Holland Mathematical Library 47, Amsterdam (1991). MR 1107298 | Zbl 0743.46082
[2] C. A. Carolan: The least concave majorant of the empirical distribution function. Can. J. Stat. 30 (2002), 317-328. DOI 10.2307/3315954 | MR 1926068 | Zbl 1012.62052
[3] G. Debreu: Least concave utility functions. J. Math. Econ. 3 (1976), 121-129. DOI 10.1016/0304-4068(76)90020-3 | MR 0411563 | Zbl 0361.90007
[4] C. A. Hall, W. W. Meyer: Optimal error bounds for cubic spline interpolation. J. Approximation Theory 16 (1976), 105-122. DOI 10.1016/0021-9045(76)90040-x | MR 0397247 | Zbl 0316.41007
[5] I. Halperin: Function spaces. Can. J. Math. 5 (1953), 273-288. DOI 10.4153/CJM-1953-031-3 | MR 0056195 | Zbl 0052.11303
[6] W. Härdle, G. Kerkyacharian, D. Picard, A. Tsybakov: Wavelets, Approximation, and Statistical Applications. Lecture Notes in Statistics 129, Springer, Berlin (1998). DOI 10.1007/978-1-4612-2222-4 | MR 1618204 | Zbl 0899.62002
[7] R. A. Jarvis: On the identification of the convex hull of a finite set of points in the plane. Inf. Process. Lett. 2 (1973), 18-21. DOI 10.1016/0020-0190(73)90020-3 | Zbl 0256.68041
[8] R. Kerman, M. Milman, G. Sinnamon: On the Brudnyĭ-Krugljak duality theory of spaces formed by the $\mathcal{K}$-method of interpolation. Rev. Mat. Complut. 20 (2007), 367-389. DOI 10.5209/rev_rema.2007.v20.n2.16492 | MR 2351114 | Zbl 1144.46058
[9] G. G. Lorentz: Bernstein Polynomials. Mathematical Expositions, no. 8. University of Toronto Press X, Toronto (1953). MR 0057370 | Zbl 0051.05001
[10] M. Mastyło, G. Sinnamon: A Calderón couple of down spaces. J. Funct. Anal. 240 (2006), 192-225. DOI 10.1016/j.jfa.2006.05.007 | MR 2259895 | Zbl 1116.46015
[11] J. Peetre: Concave majorants of positive functions. Acta Math. Acad. Sci. Hung. 21 (1970), 327-333. DOI 10.1007/BF01894779 | MR 0272960 | Zbl 0204.38002

Affiliations:   Martin Franců, Faculty of Mathematics and Physics, Charles University, Sokolovská 83, 186 75 Praha 8, Czech Republic, e-mail:; Ron Kerman, Department of Mathematics and Statistics, Brock University, 1812 Sir Isaac Brock Way, St. Catharines, Ontario L2S 3A1, Canada, e-mail:; Gord Sinnamon, Department of Mathematics, University of Western Ontario, 2004 Perth Dr, London, Ontario N6G, Canada, e-mail:

PDF available at: