Minimising the maximum distance between bounded functions for a given bounded function Let $g\in C[0,1]$ where $C[0,1]$ is the vector space of continuous functions on [0,1].
For any function $f$, define $A_f$ $= \sup\{\sqrt{(x-y)^2+(f(x)-g(y))^2}:x,y\in[0,1]\}$
Can the "sup" be replaced with "max" here?
Main question: What is inf { $A_f: f \in C[0,1] $} ? Clearly $A_f$ is always unique for a given $g$, but how many functions can give rise to a $A_f$ for a given $g$, and more importantly, how do we find them?
 A: I present my answer in three parts : 
Part I. List of short answers
Part II. The formal details and proofs.
Part III. A complete example.
 Part I : List of short answers 


*

*Is the supremum $A_f$ actually attained ? YES (as $(x-y)^2 + (f(x) - g(y))^2$ is continuous on the compact set $[0,1]^2$)

*Is the infimum ${\sf inf }_f(A_f)$ actually attained ? YES (see proof in Part II)

*Is there a unique optimal solution $f$ ? NO ( in the typical example in Part III, there are uncountably many solutions).

*How do I find the optimal solutions ? It will be clear from Part II that the condition “$f$ is optimal” is equivalent to a certain (obvious&natural) inequality system involving $f$ (called “(*)” in Part II). In the simplest cases (such as the example in Part III), this system reduces to something of the form $L\leq f \leq U$, where $L$ and $U$ are functions that we can compute from the initial data.


 Part II : The formal details and proofs 
First, note that your $A_f$ depends on $g$, so I prefer to denote it by $A_f^g$. The quantity that we are dealing with is then  $\inf_{f}A_f^g$, which I denote by $RD(f,g)$ and call  the Rubinson distance  between $f$ and $g$.  Fix $g\in C([0,1])$. For $x,y\in [0,1]$
and $c\in {\mathbb R}$, let
$$
F_1(x,c,y)=(x-y)^2+(c-g(y))^2
$$
Then $F_1$ is continuous on $[0,1] \times {\mathbb R} \times [0,1]$. Since $[0,1]$ is compact, the function
$$
F_2(x,c)={\sf max}_{y\in [0,1]} F_1(x,c,y)
$$
is well-defined and continuous on $[0,1] \times {\mathbb R}$. Also, for any $(x,y) \in [0,1]^2$, the map $F_1(x,.,y)$ is nonnegative and strictly convex on $\mathbb R$. We deduce that for any $x\in[0,1]$,$F_2(x,.)$ is also nonnegative and strictly convex on $\mathbb R$.
Now any nonnegative, strictly convex and continuous map on $\mathbb R$ which tends to $+\infty$ at both $-\infty$ and $+\infty$ attains a minimum at a  unique  point. So for each $x\in [0,1]$, $F_2(x,.)$ attains a global minimum at a unique point, which I denote by $F_3(x)$.
I claim that $F_3$ is continuous on $[0,1]$. For suppose not ; then, we would have a $x\in [0,1]$ and a sequence $(x_n)$ converging to $x$ in $[0,1]$, such that $(F_3(x_n))$ does not converge to $(F_3(x))$. By the Bolzanno-Weierstrass property, we may assume without loss of generality that $(F_3(x_n))$ converges to a value $z$ ; then $z\neq F_3(x)$ by hypothesis. For any  $n\in {\mathbb N}$,  $F_2(x_n,.)$ attains a global minimum at $F_3(x_n)$. Passing to the limit, we see that $F_2(x,.)$ attains a global minimum at $z$. But by unicity of $F_3(x)$, we must have $z=F_3(x)$, contradiction.
I claim that $F_3$ is an optimal solution. Indeed, let $m=RD(g,F_3)$. There is an $(x_0,y_0)$ in $[0,1]^2$ such that
$$
m=\sqrt{(x_0-y_0)^2+(F_3(x_0)-g(y_0))^2} =\sqrt{F_1(x_0,F_3(x_0),y_0)} \tag{1}
$$
By definition of $RD$, we must have $m \geq \sqrt{F_1(x_0,F_3(x_0),y)}$ for any $y\in [0,1]$. We deduce
$$
m=\sqrt{{\sf max}_{y\in [0,1]} F_1(x_0,F_3(x_0),y)}=\sqrt{F_2(x_0,F_3(x_0))}. \tag{2}
$$
and let  $f$ be an arbitrary function in $C([0,1])$. Then we have
$$
RD(f,g)={\sf max}_{x,y\in [0,1]} \sqrt{(x-y)^2+(f(x)-g(y))^2} = {\sf max}_{x\in [0,1]} \sqrt{F_2(x,f(x))}
\geq \sqrt{F_2(x_0,f(x_0))} \geq \sqrt{F_2(x_0,F_3(x_0))} = m = RD(F_3,g),
$$
as wished.
Also, an arbitrary function $f$ will be optimal iff $RD(f,g) \leq m$, or in other words
$$
(x-y)^2+(f(x)-g(y))^2 \leq m^2, \tag{*}
$$
for any $x,y \in [0,1]$.
 Part III : A complete example 
Let us look at $g(t)=1+2t$.
We have $F_1(x,c,y)=(x-y)^2+(c-(2y+1))^2$ and the following polynomial identities :
$$
F_1(x,c,y)=F_1(x,c,1)-5(1-y)\bigg(\frac{4}{5}.\big(\frac{9-2x}{4}-c\big)+y\bigg) \tag{3}
$$
$$
F_1(x,c,y)=F_1(x,c,0)-5y\bigg(\frac{4}{5}.\big(c-\frac{9-2x}{4}\big)+1-y\bigg) \tag{4}
$$
We deduce
$$
F_2(x,c)= \left\lbrace \tag{5}
\begin{array}{lcl}
F_1(x,c,1) = (x-1)^2+(c-3)^2, & \text{if} & c \leq \frac{9-2x}{4}, \\
F_1(x,c,0) = x^2+(c-1)^2, & \text{if} & c \geq \frac{9-2x}{4}
\end{array}
\right.
$$
And hence
$$
F_3(x)= \frac{9-2x}{4}, m=\frac{5}{4}. \tag{6}
$$
Making (*) explicit, we see that an $f\in C[0,1]$ will be optimal iff
$$
2- \sqrt{\frac{25}{16}-(1-x)^2} \leq f(x) \leq  \sqrt{\frac{25}{16}-x^2}, \tag{7}
$$
for any $x\in [0,1]$.
So the optimal solutions will be the solutions whose curve stays between the curves defined by the left-hand and right-hand side in $(7)$.
