# Padua points

In polynomial interpolation of two variables, the Padua points are the first known example (and up to now the only one) of a unisolvent point set (that is, the interpolating polynomial is unique) with minimal growth of their Lebesgue constant, proven to be $O(\log ^{2}n)$. Their name is due to the University of Padua, where they were originally discovered.
The points are defined in the domain $[-1,1]\times [-1,1]\subset \mathbb {R} ^{2}$. It is possible to use the points with four orientations, obtained with subsequent 90-degree rotations: this way we get four different families of Padua points.

## The four families

We can see the Padua point as a "sampling" of a parametric curve, called generating curve, which is slightly different for each of the four families, so that the points for interpolation degree $n$ and family $s$ can be defined as
    ${\text{Pad}}_{n}^{s}=\lbrace \mathbf {\xi } =(\xi _{1},\xi _{2})\rbrace =\left\lbrace \gamma _{s}\left({\frac {k\pi }{n(n+1)}}\right),k=0,\ldots ,n(n+1)\right\rbrace .$
Actually, the Padua points lie exactly on the self-intersections of the curve, and on the intersections of the curve with the boundaries of the square $[-1,1]^{2}$. The cardinality of the set $\operatorname {Pad} _{n}^{s}$ is |Pad$_n$$^s$⁡|=((n+1)(n+2))/2 {\textstyle |\operatorname {Pad} _{n}^{s}|={\frac {(n+1)(n+2)}{2}}}. Moreover, for each family of Padua points, two points lie on consecutive vertices of the square $[-1,1]^{2}$, $2n-1$ points lie on the edges of the square, and the remaining points lie on the self-intersections of the generating curve inside the square.
The four generating curves are closed parametric curves in the interval $[0,2\pi ]$, and are a special case of Lissajous curves.

### The first family

The generating curve of Padua points of the first family is
    $\gamma _{1}(t)=[-\cos((n+1)t),-\cos(nt)],\quad t\in [0,\pi ].$
If we sample it as written above, we have:
    $\operatorname {Pad} _{n}^{1}=\lbrace \mathbf {\xi } =(\mu _{j},\eta _{k}),0\leq j\leq n;1\leq k\leq \lfloor {\frac {n}{2}}\rfloor +1+\delta _{j}\rbrace ,$
where $\delta _{j}=0$ when $n$ is even or odd but $j$ is even, $\delta _{j}=1$ if $n$ and $k$ are both odd
with
    $\mu _{j}=\cos \left({\frac {j\pi }{n}}\right),\eta _{k}={\begin{cases}\cos \left({\frac {(2k-2)\pi }{n+1}}\right)&j{\mbox{ odd}}\\\cos \left({\frac {(2k-1)\pi }{n+1}}\right)&j{\mbox{ even.}}\end{cases}}$
From this follows that the Padua points of first family will have two vertices on the bottom if $n$ is even, or on the left if $n$ is odd.

### The second family

The generating curve of Padua points of the second family is
    $\gamma _{2}(t)=[-\cos(nt),-\cos((n+1)t)],\quad t\in [0,\pi ],$
which leads to have vertices on the left if $n$ is even and on the bottom if $n$ is odd.

### The third family

The generating curve of Padua points of the third family is
    $\gamma _{3}(t)=[\cos((n+1)t),\cos(nt)],\quad t\in [0,\pi ],$
which leads to have vertices on the top if $n$ is even and on the right if $n$ is odd.

### The fourth family

The generating curve of Padua points of the fourth family is
    $\gamma _{4}(t)=[\cos(nt),\cos((n+1)t)],\quad t\in [0,\pi ],$
which leads to have vertices on the right if $n$ is even and on the top if $n$ is odd.

## The interpolation formula

The explicit representation of their fundamental Lagrange polynomial is based on the reproducing kernel $K_{n}(\mathbf {x} ,\mathbf {y} )$, $\mathbf {x} =(x_{1},x_{2})$ and $\mathbf {y} =(y_{1},y_{2})$, of the space $\Pi _{n}^{2}([-1,1]^{2})$ equipped with the inner product
    $\langle f,g\rangle ={\frac {1}{\pi ^{2}}}\int _{[-1,1]^{2}}f(x_{1},x_{2})g(x_{1},x_{2}){\frac {dx_{1}}{\sqrt {1-x_{1}^{2}}}}{\frac {dx_{2}}{\sqrt {1-x_{2}^{2}}}}$
defined by
    $K_{n}(\mathbf {x} ,\mathbf {y} )=\sum _{k=0}^{n}\sum _{j=0}^{k}{\hat {T}}_{j}(x_{1}){\hat {T}}_{k-j}(x_{2}){\hat {T}}_{j}(y_{1}){\hat {T}}_{k-j}(y_{2})$
with ${\hat {T}}_{j}$ representing the normalized Chebyshev polynomial of degree $j$ (that is, ${\hat {T}}_{0}=T_{0}$ and ${\hat {T}}_{p}={\sqrt {2}}T_{p}$, where $T_{p}(\cdot )=\cos(p\arccos(\cdot ))$ is the classical Chebyshev polynomial of first kind of degree $p$). For the four families of Padua points, which we may denote by $\operatorname {Pad} _{n}^{s}=\lbrace \mathbf {\xi } =(\xi _{1},\xi _{2})\rbrace$, $s=\lbrace 1,2,3,4\rbrace$, the interpolation formula of order $n$ of the function $f\colon [-1,1]^{2}\to \mathbb {R} ^{2}$ on the generic target point $\mathbf {x} \in [-1,1]^{2}$ is then
    ${\mathcal {L}}_{n}^{s}f(\mathbf {x} )=\sum _{\mathbf {\xi } \in \operatorname {Pad} _{n}^{s}}f(\mathbf {\xi } )L_{\mathbf {\xi } }^{s}(\mathbf {x} )$
where $L_{\mathbf {\xi } }^{s}(\mathbf {x} )$ is the fundamental Lagrange polynomial
    $L_{\mathbf {\xi } }^{s}(\mathbf {x} )=w_{\mathbf {\xi } }(K_{n}(\mathbf {\xi } ,\mathbf {x} )-T_{n}(\xi _{i})T_{n}(x_{i})),\quad s=1,2,3,4,\quad i=2-(s\mod 2).$
The weights $w_{\mathbf {\xi } }$ are defined as
    $w_{\mathbf {\xi } }={\frac {1}{n(n+1)}}\cdot {\begin{cases}{\frac {1}{2}}{\text{ if }}\mathbf {\xi } {\text{ is a vertex point}}\\1{\text{ if }}\mathbf {\xi } {\text{ is an edge point}}\\2{\text{ if }}\mathbf {\xi } {\text{ is an interior point.}}\end{cases}}$