# What are the Chebyshev sets for the taxicab metric?

A set of points $$S \subseteq \mathbb{R}^n$$ is called a Chebyshev set if the metric projection w.r.t $$S$$ is single-valued. That is, for every point $$x\in \mathbb{R}^n$$, there is a unique point $$y\in S$$ that minimizes the distance to $$x$$.

WHen the distance is measured by the Euclidean metric ($$\ell_2$$). it is known that $$S$$ is a Chebyshev set if and only if it is closed and convex.

MY QUESTION: suppose the distance is measured by the taxicab metric ($$\ell_1$$). What are the Chebyshev sets in this case?

• Every closed and convex subset is a Proximinal set, i.e. for every point $x$ the metric projection $P(x)$ is non empty but it need not be Chebyshev. This is because the $\ell_1$ norm is not rotund. Commented Jun 21 at 20:51

Surprisingly to me, it appears that $$S$$ need not be convex!

Let $$\| \cdot \|$$ be any norm on $$\mathbb{R}^n$$ and consider the induced metric $$d(x, y) = \| x - y \|$$. I have the following geometric picture in mind: to calculate the projection wrt $$d$$ from a point $$x$$ onto a set $$S$$, we consider the balls $$B_r(x)$$ of various radii around $$x$$. These are scaled copies of the unit ball $$B$$ and we can imagine the ball scaling up bigger and bigger until the first time it touches $$S$$.

For example if $$n = 2$$ and we take the $$\ell^1$$ norm then the unit ball is the familiar square rotated $$45^{\circ}$$ and we are just seeing what happens when we scale this square until it touches $$S$$. Now consider the following choice of $$S$$: the "bent half-plane" given by all points to the left of the rays

$$L_1 = \{ (x, 2x) : x \ge 0 \}$$

and

$$L_2 = \{ (x, -2x) : x \ge 0 \}.$$

Then I claim that $$S$$ is Chebyshev with respect to the $$\ell^1$$ norm (but is not convex). The projection from a point $$p$$ is obtained, as above, by scaling up the rotated square until it touches $$S$$, which always happens at the point obtained by moving directly left from $$p$$ (as in, parallel to the $$x$$-axis) until we touch $$S$$. In the $$\ell^2$$ norm $$S$$ is not Chebyshev because, for example, the point $$(1, 0)$$ does not have a unique projection: when we start with a circle around that point and scale up it touches $$S$$ at two points. But the western corner of the $$\ell^1$$ unit sphere has a sharp enough angle that this can't happen here.

Generally it seems that $$S$$ can be "bent" in various directions depending on "how sharp the corners are" of the unit ball of the norm $$\| \cdot \|$$ in those directions. Hopefully you can see geometrically how this should work although writing down precisely what this means seems tricky.

I think it should still be true that a sufficient, although not necessary, condition is that $$S$$ is closed, convex, and furthermore does not contain a "hyperplane segment" parallel to any hyperplane segment of the unit sphere of $$\| \cdot \|$$. (For example, if we bend the lines $$L_1, L_2$$ above until they have slope $$\pm 1$$, matching the slopes of the sides of the rotated square, then the projection of $$(1, 0)$$ will no longer be unique.)