When doing simple linear interpolation on a data set in $\mathbb{R}^2$, I just sort the points by one co-ordinate and then do piecewise interpolation between a point and its successor in the sorted data set.
How would I do this in $\mathbb{R}^3$, and generally in $\mathbb{R}^k$?
How would I know which points to "connect"? (In the two-dimensional case the sorting takes care of that.)
How complex would it be to calculate such simple interpolations?