Given a subset $S\subseteq \mathbb{R}^n$ and a metric $d$, the [metric projection][1] associated with $S$ is a function that maps each point $x\in \mathbb{R}^n$ to the set of nearest elements in $S$, that is $p_S(x) = \arg \min_{y\in S} d(x,y)$.

Suppose we associate with each point $x\in \mathbb{R}^n$, a closed set $S(x) \subseteq \mathbb{R}^n$. 
Then we can compute, for every two points $x,y\in \mathbb{R}^n$, their *mutual metric projection*:
$$
q_S(x,y) = p_{S(y)}(x) \cap p_{s(X)}(y).
$$
That is, the intersection of the points in $S(y)$ nearest to $x$ and the points in $S(x)$ nearest to $y$.

**What are the functions $S$ for which the set $q_S(x,y)$ is nonempty for all $x,y$?**

One trivial example is a constant singleton function: if $S(x)\equiv \{c\}$ for all $x\in \mathbb{R}^n$, then $q_S(x,y) = \{c\}$ for all $x,y\in \mathbb{R}^n$.

A less trivial example, for $n=1$, is the function $S$ that returns, for each $x\in\mathbb{R}$, the half-line to the left of $x$: $S(x) = (-\infty, x]$. In this case, $q_S(x,y) = \{\min(x,y) \}$ for all $x,y \in \mathbb{R}$.

A third example is the function $S$ that returns, for each $x\in\mathbb{R}$, the interval $[x,c]$, for some constant point $c$. In this case, $q_S(x,y) = \{\text{median}(x,y,c)\}$.

A non-example is is the function $S$ that returns, for each $x\in\mathbb{R}$, the interval $[x,x+1]$. For example, $q_S(3, 6) = \emptyset$.

**What is a characterization of all functions $S$ for which $q_S$ is non-empty?**

I am mainly interested in the case when $d$ is the $\ell_1$ metric on $\mathbb{R}^n$, but other metrics are also interesting.


  [1]: https://en.wikipedia.org/wiki/Metric_projection