Return to 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?

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.

Given a subset $S\subseteq \mathbb{R}^n$ and a metric $d$, 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)$.

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.

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?

Given a subset $S\subseteq \mathbb{R}^n$ and a metric $d$, 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)$.

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 some $\ell_p$ metric on $\mathbb{R}^n$.

Given a subset $S\subseteq \mathbb{R}^n$ and a metric $d$, 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)$.

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.