About the maximum degree of multivariate polynomial interpolation

Question

It is well known that in the univariate case, to interpolate $k$ points in $\mathbb{R}$, we need to use a polynomial of degree $k-1$.

My question is about multivariate polynomial interpolation in higher dimension. We are given $k$ points $x_1,\ldots,x_k$ in $\mathbb{R}^d$. Define the max-deg of a multivariate polynomial to be the maximum exponent of any variable. For example, the max-deg of the linear function $x_1+x_2+x_3$ is 1 and the max-deg $x_1^2+x_2$ is 2. My question is: given $x_1,\ldots,x_n$, what is the minimum $d$ such that for any $y_1,\ldots, y_d$, there is a polynomial $P$ of max-deg $d$ such that $P(x_i)=y_i\forall i$. The answer should really depend on the configuration of $x_1 ,\ldots,x_k$. For example, if $x_1 ,\ldots,x_k$ are linearly independent, we only need max-deg to be 1 (i.e., we can use a linear function to intepolate it).

Has the same problem (or some thing similar) been studied before?

Answer 1

I think relevant results are summarized in part 2 "Haar spaces and multivariate polynomials" of the "Scattered Data Approximation" by Holger Wendland.

One would hope to be able to interpolate data sites $X = \{x_1,\dots, x_Q \}$ with a polynomial from $\pi_m(\mathbb{R}^d)$ when $Q=\dim \pi_m(\mathbb{R}^d)={m+d\choose d}$. Here $m$ is your "max-deg".

It is proven (Mairhuber–Curtis) to be generally impossible unless unisolvency of data sites is ensured: for example, when they are on a more or less regular grid, interpolation with multivariate polynomials is possible.