Given two sequences $a_0 \leq a_1 \leq \ldots \leq a_{n-1}$ and $b_0 \leq b_1 \leq \ldots \leq b_{n-1}$. We want to find a one-to-one mapping $\pi:[n-1] \rightarrow [n-1]$ such that $$ \max \min_{i} |a_i - b_{\pi(i)}|. $$ I want to show that there is an optimal $\pi$ that satisfies $\pi(i) = i + k \mod n$ for some $k$.
I have a proof, but it is rather ugly and tedious case-by-case type.
Consider an example case. Suppose $\pi(i + 1) > \pi(i) + 1 \mod n$ for some $i$ and suppose $a_i \leq b_{\pi(i)}$ and $\pi(i + 1) < n$.
We argue that we can change the mapping so that $i+1$ is mapped to $\pi(i) + 1$ while keeping the minimum absolute difference just as large.
Then, there must be some $j$ such that $\pi(j) = \pi(i) + 1$.
If $j > i+1$, we can construct a new mapping $\pi'$ by letting $\pi'(i) = \pi(i) + 1$, $\pi'(j) = \pi(i)$ while keeping all other mapping the same. Note that $|a_i - b_{\pi(i)+1}| \geq |a_i - b_{\pi(i)}|$ and $|a_j - b_{\pi(i)}| \geq |a_j - b_{\pi(i)+1|}$. We therefore have a matching that is at least as good. After $\pi \leftarrow \pi'$, $i$ is now mapped to a point closer to $i+1$.
If $j < i$, we construct a new matching $\pi'$ by letting $\pi'(j) = \pi(i)$ and $\pi'(i)=\pi(i+1)$ and keep all other other mappings the same. Note that $|a_j - b_{\pi(i)}|, |a_i - b_{\pi(i)+1}| \geq |a_i - b_{\pi(i)}|$. We therefore have a matching that is at least as good. After $\pi \leftarrow \pi'$, $i$ is now mapped to a point closer to $i+1$.
We can handle other cases similarly. This process eventually leads to $\pi(i+1) = \pi(i)+1 \mod n$.
However, I think I must have missed some simple observations for a simpler and shorter proof.
I wonder if a shorter and less tedious proof is possible.