Thread: Maximally separate points in concentric circles in the $L_1$ norm

1. Maximally separate points in concentric circles in the $L_1$ norm

Given two concentric circles $X_1$ (green), $X_2$ (red) with radii $1$ and $2$, respectively, it is clear that the set of points that maximally separate the two circles in the $L_2$ norm is the circle with radius $\frac{3}{2}$ (blue).

I would like to understand how to construct the set of points that maximally separate $X_1$ and $X_2$ in the $L_1$ norm. I understand the $L_1$ ball generally forms a diamond, but I am somewhat lost trying to figure out how to use this to maximally separate the two circles.

Note: I define the maximum separator as the set of points that have two or more closest points, in the $L_p$ norm, on distinct circles ($X_1$ and $X_2$).

2. Re: Maximally separate points in concentric circles in the $L_1$ norm

Originally Posted by skamoni
Given two concentric circles $X_1$ (green), $X_2$ (red) with radii $1$ and $2$, respectively, it is clear that the set of points that maximally separate the two circles in the $L_2$ norm is the circle with radius $\frac{3}{2}$ (blue).

I would like to understand how to construct the set of points that maximally separate $X_1$ and $X_2$ in the $L_1$ norm. I understand the $L_1$ ball generally forms a diamond, but I am somewhat lost trying to figure out how to use this to maximally separate the two circles.

Note: I define the maximum separator as the set of points that have two or more closest points, in the $L_p$ norm, on distinct circles ($X_1$ and $X_2$).

You need to give more clarity in your definition. What does it mean for a set to have two or more closest points on the distinct circles? I can't figure out what you are trying to get at.

3. Re: Maximally separate points in concentric circles in the $L_1$ norm

Originally Posted by Walagaster
You need to give more clarity in your definition. What does it mean for a set to have two or more closest points on the distinct circles? I can't figure out what you are trying to get at.

How do I define a separator?

Let $\Delta$ be a set of points in the plane. I say $\Delta$ is a separator of $X_1$ and $X_2$ if any continuous function $f$ that passes through $X_1$ and $X_2$ must necessarily pass through $\Delta$.

How do I define a maximum separator?

Let $\Delta$ be any separator of $X_1$ and $X_2$. Pick a point $x \in \Delta$ and imagine growing a $\|.\|_p$-ball centred at $x$ (i.e. consider the ball $B_{\epsilon}(x):=\{z \mid \|z-x\|_p \leq \epsilon\}$). I call $\Delta$ a maximum separator, if $\forall x \in \Delta$ the following holds: $\forall \epsilon > 0$, $\exists m_1, m_2 \in B_{\epsilon}(x)$ and points $y_1, y_2 \in X_1 \bigcup X_2$, such that if $y_1$ is the point that minimizes $\|m_1 - y\|_p$ ( where $y \in X_1 \bigcup X_2$ ), then $y_1 \in X_1$, and equivalently if $y_2$ is the point that minimizes $\|m_2 - y\|_p$ ( where $y \in X_1 \bigcup X_2$ ), then $y_2 \in X_2$.

An example of a separator that is not maximal?

Lets take the extreme example of $X_1$ being a separator. Then clearly there exists $x \in X_1$ and some $\epsilon > 0$ such that for all points $z$ in $B_{\epsilon}(x)$ the points
$y \in X_1 \bigcup X_2$ that minimize $\|z - y\|_p$ all lie on $X_1$ (i.e. $y \in X_1$ and $y \notin X_2$)