-Functions Piecewise-linear Approximation from Noisy and Hermite Data

Fig. 1. A function is represented with noisy data points. The lower and upper convex hull crudely approximate the data by fitting lines. Replacing the lines with parabolas of the form -1 2 𝛼𝑥 2 creates more detailed lower hulls as 𝛼 increases (from left to right). The function can be approximated as the mid-contour of the lower and upper 𝛼-hull

We introduce 𝛼-functions, providing piecewise linear approximation to given data as the difference of two convex functions. The parameter 𝛼 controls the shape of a paraboloid that is probing the data and may be used to filter out noise in the data. The use of convex functions enables tools for efficient approximation to the data, adding robustness to outliers, and dealing with gradient information. It also allows using the approach in higher dimension. We show that 𝛼-functions can be efficiently computed and demonstrate their versatility at the example of surface reconstruction from noisy surface samples.