How to determine the smallest interpolation degree required?

Question

Given a set of $n$ points $(x_k, y_k)\ (k\in\{1,...,n\})$, of course a polynomial of degree $n$ can fit all points. However, in some cases the coefficient of the higher degrees actually vanish and one obtains a polynomial of degree $m<n$, e.g. four points that all lie on a parabola. Aside from actually calculating the interpolating polynomial, is there any simpler way to determine the smallest polynomial degree $m\le n$ required to obtain a specific set of points?

Answer 1

There cannot really be a way to find the required degree that is significantly simpler than actually calculating the interpolating polynomial. Heuristics: Assume there is such a simple method, then value of the interpolating polynomial at $x$ can be found by determining the single $y$ for which the interpolating poylnomial for the $n$ geiven points polus $(x,y)$ is of degree $<n$.

Answer 2

You could set up a degree $n-1$ polynomial with unknown coefficients, and write down the set of linear equations that the points give you, and put the linear equations into row echelon form or something.