Czechoslovak Mathematical Journal, online first, 23 pp.

A new algorithm for approximating the least concave majorant

Martin Franců, Ron Kerman, Gord Sinnamon

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

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:

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 2010): 26A51, 52A41, 46N10

DOI: 10.21136/CMJ.2017.0408-16

Full text available as PDF.

[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

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at
Subscribers of Springer need to access the articles on their site, which is

[List of online first articles] [Contents of Czechoslovak Mathematical Journal] [Full text of the older issues of Czechoslovak Mathematical Journal at DML-CZ]