1. A method for performing interpolation of a point of interest producing an approximated function value of said point of interest using an input data set comprising: determining distances between said point of interest and points in said input data set; sorting said distances; selecting a predetermined number of points in said input data set which are closest to said point of interest in accordance with said distances; determining whether said point of interest is one of: enclosed within a simplex and on a boundary of the simplex, said simplex formed by a combination of n&plus;1 points selected from said predetermined number of points, said n&plus;1 points forming vertices of said simplex, n being a dimension of points in said input data set; and if there is a simplex enclosing said point of interest or including said point of interest on its boundary, fitting a linear surface to said vertices of said simplex in accordance with a linear function, and evaluating said linear function at said point of interest to determine said approximated function value representing the approximation of said linear function at said point of interest.