Example 10 Given a positive integer $n \geqslant 3$. Find the smallest integer $k$ such that for any $n$ points $A_{i}\left(x_{i}, y_{i}\right)$ in the plane, no three of which are collinear, and any $n$ real numbers $c_{i}$, there always exists a bivariate real polynomial $P(x, y)$ of degree not exceeding $k$ satisfying $P\left(x_{i}, y_{i}\right)=c_{i}$.
【Analysis】Study the problem, starting from the univariate case. When all are univariate polynomials, it becomes an interpolation formula. Consider the origin of the Lagrange formula: it includes $n$ expressions that can make:
$$
\begin{array}{l}
f\left(x_{i}\right)=1, \\
f\left(x_{1}\right)=\cdots=f\left(x_{i-1}\right)=f\left(x_{i+1}\right) \\
=\cdots=f\left(x_{n}\right)=0
\end{array}
$$

The expression is $\frac{\left(x-x_{2}\right) \cdots\left(x-x_{n}\right)}{\left(x_{1}-x_{2}\right) \cdots\left(x_{1}-x_{n}\right)}$, which is the key to completing the interpolation.

For bivariate polynomials, the basic components are $a x+b y+d$. Consider constructing a formula similar to the Lagrange interpolation formula.
Let $t_{i}=a x_{i}+b y_{i}+d_{i}, t=a x+b y+d$.
Construct $\frac{\left(t-t_{2}\right)\left(t-t_{3}\right) \cdots\left(t-t_{n}\right)}{\left(t_{1}-t_{2}\right)\left(t_{1}-t_{3}\right) \cdots\left(t_{1}-t_{n}\right)}$.
At this point, a problem is discovered: since the parameters $a, b, d$ in $t_{i}$ and $t$ are arbitrary, two $t_{i}$ can be combined (in fact, $t-t_{i}$ represents a line passing through $\left(x_{i}, y_{i}\right)$, and $a, b, d$ can be adjusted so that $t-t_{i}$ passes through two of the $n$ points).
Thus, the following construction is obtained:
When $2+n$, let
$\left(x_{2}, y_{2}\right), \left(x_{3}, y_{3}\right)$ determine
the line $l_{1}: a_{1} x+b_{1} y+d_{1}=0$;
$\left(x_{4}, y_{4}\right), \left(x_{5}, y_{5}\right)$ determine
the line $l_{2}: a_{2} x+b_{2} y+d_{2}=0$;
$\qquad$
$\left(x_{n-1}, y_{n-1}\right), \left(x_{n}, y_{n}\right)$ determine
the line $l_{k}: a_{k} x+b_{k} y+d_{k}=0\left(k=\frac{n-1}{2}\right)$.
Let $f_{1}(x, y)=\frac{\prod_{i=1}^{k}\left(a_{i} x+b_{i} y+d_{i}\right)}{\prod_{i=1}^{k}\left(a_{i} x_{1}+b_{i} y_{1}+d_{i}\right)}$, and the construction of other $f_{j}(x, y)$ is completely similar.
Then let $P(x, y)=\sum_{i=1}^{n} c_{i} f_{i}(x, y)$.
At this point, $\operatorname{deg} P=\frac{n-1}{2}$.
When $21 n$, take another point to form $n+1$ points, and construct similarly, then $\operatorname{deg} P=\frac{n}{2}$.

Finally, find $n$ points, showing that at least $\left[\frac{n}{2}\right]$ times are needed, where $[x]$ represents the greatest integer not exceeding the real number $x$. To reduce to a univariate polynomial, determine a relationship between $y$ and $x$, $y=x^{2}$, and take $n$ points as $(1,1)$, $(2,4),(3,9), \cdots,\left(n, n^{2}\right)$. At this time,
$$
P\left(x_{i}, y_{i}\right)=P\left(x_{i}, x_{i}^{2}\right).
$$

If $\operatorname{deg} P<\left[\frac{n}{2}\right]$, then
the degree of the univariate polynomial $g(x)$
$$
\leqslant 2\left(\left[\frac{n}{2}\right]-1\right) \leqslant n-2.
$$

Assigning values of 0 at $(1,1),(2,4), \cdots,\left(n-1,(n-1)^{2}\right)$, we get $g(x) \equiv 0$, and assigning a value of 1 at $\left(n, n^{2}\right)$ leads to a contradiction.
In summary, $k_{\min }=\left[\frac{n}{2}\right]$.