Mutual metric projection

Question

Given a subset $S\subseteq \mathbb{R}^n$, the metric projection 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)$, where $d$ is the Euclidean distance.

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?

Note: for simplicity I mentioned that $d$ is the Euclidean metric, but I am also interested in other metrics such as the taxicab metric.

Answer 1

I started to investigate properties of possible required map $S$, but they are hard to grasp, so my vision of them is very coarse, see the propositions below. But I shall try to use them to refine descriptions of possible maps $S$ farther. Also I am going to discuss your question at our today's seminar with Taras Banakh. A long time ago we investigated a bit similar maps, see, for instance, this paper. So I hope we shall be able to advance in the investigation of possible maps $S$ too. Also I am going to suggest to Taras Banakh to give your question to his student as a research topic for a course paper.

Proposition 1. For each $x,y\in\mathbb R^n$, $S(x)\cap S(y)\ne\varnothing$.

Proof. The set $S(x)\cap S(y)$ contains the nonempty set $q(x.y)$. $\square$

Proposition 2. For each $x\in\mathbb R^n$, $y\in S(x)$ and $z\in S(y)$ we have $d(x,z)\ge d(x,y)$.

Proof. Since $y\in S(x)$, $p_{S(x)}(y)=\{y\}$. So $p_{S(y)}(x)\supset \{y\}$, therefore there is no point $z\in S(y)$ with $d(x,z)<d(x,y)$. $\square$

Now we can show the following dichotomy, already illustrated by your examples.

Proposition 3. The family $\{S(x):x\in\mathbb R^n\}$ consists of bounded sets or of unbounded sets.

Proof. Suppose for a contradiction that there exist $x,y\in\mathbb R^n$ such that $S(x)$ is bounded and $S(y)$ is unbounded. Pick any point $z\in S(y)$ such that $d(y,z)>\sup_{t\in S(x)} d(y,t)$. By Proposition 1, there exists a point $t\in S(x)\cap S(z)$. By Proposition 2, $d(y,t)\ge d(y,z)$, a contradiction. $\square$

Answer 2

This is a horribly long and convoluted answer addressing one extremely specific case: $n = 1$ and $S(x)$ is an interval for any $x$. Since in $\mathbb{R}$, a subset is an interval iff it is connected iff it is convex, this might shed some light on the more general case where $S(x)$ is assumed connected convex but $n$ may not be $1$.

I claim that, in case $S(x)$ is always an interval in $\mathbb{R}$, the following are all possible $S$:

1. In case $S(x)$ are all bounded, then there exists $c \in \mathbb{R}$, $d \in [-\infty, c]$, $e \in [c, \infty]$, s.t.

$$S(x) = \begin{cases} [d, c] &, \text{ if }x \leq d\\ [x, c] &, \text{ if }d < x \leq c\\ [c, x] &, \text{ if }c < x \leq e\\ [c, e] &, \text{ if }x > e \end{cases}$$

and any such choice of $c, d, e$ yields an $S$ that satisfies the requisite condition.

2. In case $S(x)$ are all unbounded, then either there exists $e \in (-\infty, \infty]$, s.t.

$$S(x) = \begin{cases} (-\infty, x] &, \text{ if }x \leq e\\ (-\infty, e] &, \text{ if }x > e \end{cases}$$

and any such choice of $e$ yields an $S$ that satisfies the requisite condition; or, there exists $d \in [-\infty, \infty)$, s.t.

$$S(x) = \begin{cases} [d, \infty) &, \text{ if }x \leq d\\ [x, \infty) &, \text{ if }x > d \end{cases}$$

Note that by Alex’s answer, we already have $S(x)$ are either all bounded or all unbounded, so any $S$ falls within one of the above two situations.

I’ll leave you to check that all $S$ defined above indeed stiasfy the requisite condition. I’ll instead just prove the necessity.

For notational simplicity, if $I$ is an interval, we shall let $L(I)$ be its left endpoint (including possibly $-\infty$) and $R(I)$ be its right endpoint (including possibly $\infty$).

As $\varnothing \neq q(x, y) \subset S(x) \cap S(y)$ is nonempty for any $x, y$, Helly's theorem for $d=2$ implies that any finitely many $S(x)$ intersect nontrivially.

For notational simplicity, we note that in our current case, $p_{S(x)}(y)$ is always a singleton, so I’ll simply write $p_x(y)$ for the unique point in $p_{S(x)}(y)$. The condition $q(x, y) \neq \varnothing$ is simply equivalent to saying $p_x(y) = p_y(x)$ for all $x, y$.

For the bounded case, by compactness and the fact that any finitely many $S(x)$ intersect nontrivially, we must have $\cap_{x \in \mathbb{R}} S(x) \neq \varnothing$.

Lemma: $\cap_{x \in \mathbb{R}} S(x)$ is a singleton.

Proof: Let $c_0, c_1 \in \cap_{x \in \mathbb{R}} S(x)$. Then because $c_i \in \cap_{x \in \mathbb{R}} S(x) \subset S(c_{1 - i})$, we have $c_1 = p_{c_0}(c_1) = p_{c_1}(c_0) = c_0$. $\square$

Let $c$ denote the unique element of $\cap_{x \in \mathbb{R}} S(x)$. In particular, $c \in S(x)$ for all $x$, so $p_x(c) = c$ for all $x$. Now, we first observe that $S(c) = \{c\}$. Indeed, if $d \in S(c)$, then $c = p_d(c) = p_c(d) = d$. Next, for any $x < c$, we claim that $S(x)$ contains no point strictly larger than $c$. Indeed, assume to the contrary that $y > c$, $y \in S(x)$, then $p_y(x) = p_x(y) = y$, but $c \in S(y)$ is closer to $x$ than $y$, a contradiction. To put it another way, $R(S(x)) = c$. Similarly, for any $x > c$, $S(x)$ does not contain any point strictly smaller than $c$, i.e., $L(S(x)) = c$.

We also observe that, for any $x < c$, $L(S(x)) \geq x$. Indeed, assume to the contrary that $L(S(x)) < x$. Then $L(S(x))) = p_x(L(S(x))) = p_{L(S(x))}(x)$. In particular, the interval $S(L(S(x)))$ contains both $L(S(x))$ and $c$, so as $L(S(x)) < x < c$, we must have $x \in S(L(S(x)))$, so $p_{L(S(x))}(x) = x$, a contradiction.

If for all $x < c$, we have $L(S(x)) = x$, then $S(x) = [x, c]$ for all $x < c$ and we may pick $d = -\infty$. If, on the contrary, there exists an $x < c$ s.t. $L(S(x)) > x$, then let $d = L(S(x))$. As $c \in S(x)$, $d \leq c$. Now, for any $y \leq d$, we have $d = p_x(y) = p_y(x)$. As $R(S(y)) = c$, this means $L(S(y)) = d$, i.e., $S(y) = [d, c]$ for all $y \leq d$. On the other hand, for any $d < y < c$, so $y \in S(x)$, we have $y = p_x(y) = p_y(x)$, so similarly $S(y) = [y, c]$ for all $d < y < c$. The consideration for points on the RHS of $c$ is similar. This proves the case for bounded $S(x)$.

The unbounded case is essentially similar. The trick is to compactify $\mathbb{R}$ by adding two points, $-\infty$ and $\infty$. Then we add to unbounded intervals the apppropriate point or points at infinity to compactify them as well. Now that everything is compact, we can again say $\cap_{x \in \mathbb{R}} S(x)$ is nonempty. Since it is an interval, if it contains more than one point, it must contain more than one finite (real) points, so the same argument shows $\cap_{x \in \mathbb{R}} S(x)$ is a singleton. It cannot be a point $c \in \mathbb{R}$, as otherwise the same argument as above shows $S(c) = \{c\}$, so we would be back in the bounded case. So either $\cap_{x \in \mathbb{R}} S(x) = \{-\infty\}$, or $\cap_{x \in \mathbb{R}} S(x) = \{\infty\}$. The argument from this point onwards is very similar to the bounded case, so I’ll leave it to you to check.