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

The problem of fitting n 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/) 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.