Let $x_1<x_2< \ldots <x_n$ be $n$ real numbers, and let $y_1,y_2,\ldots,y_n$ be real values to be interpolated. Let $r\leq n$. For any $I\subseteq \lbrace 1,2,\ldots,n\rbrace$ of cardinality $r$, we may form the Lagrange polynomial $L_I$ from the pairs $(x_i,y_i)_{i\in I}$ ; this will be the unique polynomial of degree $<r$ such that $L_I(x_i)=y_i$ for any $i\in I$.
Is it always the case that at least one of these $L_I$ satisfies $L_I(x_j) \leq y_j$ for any $j$ ? This can be seen to be true in the “small” cases $r=1,2$ or $n$.
Remark : geometrically, the $r=2$ case means that for any finite collection of points in the plane, there will be a straight line passing through two of those points and staying below all the other points. This will be a “lower” edge of the convex hull of the points.
I think this should work, by induction on $r$ :
For $r=1$ we have to pick $I_1 = \{i_1\}$ where $y_{i_1} = \min \{ y_1 \ldots y_n\}$, and $L_{I_1} = y_{i_1}$.
Suppose you have a subset $I_r$ of size $r$ and a polynomial $L_{I_r}$ passing through $(x_i,y_i)$ for $i \in I_r$ and for which $L_{I_r}(x_j) \le y_j$ for $y \notin I_r$. We have to add to $L_{I_r}$ a polynomial of the form $\lambda \prod_{i \in I_r}(x-x_i)$. We pick the smallest $|\lambda|$ that meets another point : for each $(x_j,y_j)$ we compute $\lambda_j = (y_j - L_{I_r}(x_j))/\prod_{i \in I_r} (x_j-x_i)$. We pick the $i_{r+1}$ that minimizes $|\lambda_{i_{r+1}}|$, then $I_{r+1} = I \cup \{i_{r+1}\}$, and $L_{I_{r+1}} = L_{I_r} + \lambda_{i_{r+1}} \prod_{i \in I_r} (x-x_i)$