An O(n)O(n) algorithm for weighted least squares regression by integer quasi-convex and unimodal or umbrella functions

The problem of fitting nn data points by an integer quasi-convex (also quasi-concave, umbrella or unimodal) function using the weighted least squares distance function is considered. An algorithm of linear time (O(n)O(n)) worst-case complexity and thus optimal is constructed for computing a best fit. This problem arises in the context of curve fitting or statistical estimation.