Yet, a modification of 1-NN different from k-NN maintains its interpolating property while achieving near-optimal excess risk, at least in when the dimension is high. The algorithm is simplicial interpolation [1]}
analyzed statistically in [2]}.
Consider a triangulation of the data, \({\mathbf {x}}_1,\ldots ,{\mathbf {x}}_n\) , that is a partition of the convex hull of the data into a set of \(d\) -dimensional simplices so that:
