The Answer to TYI (57): In Dimension Three or More, Intuitive Norms are Euclidean

Combinatorics and more 2025-01-10

Consider $\mathbb R^n$ equipped with a norm. Given a finite set of points $K$ and a point $x$ , we consider $T(x,K)$ , the sum of distances from $x$ to the points in $K$ . Next we consider the set of points $M(K)$ that attain the minimum of $T(x,K)$ . Such a point is called a geometric median of $K$ with respect to the norm. We say that the norm is intuitive if $M(K)$ has non empty intersection with the convex hull of $K$ .

For the Euclidean norm, the geometric median is also known as the Fermat-Weber point, the Torricelli point, and Haldane’s median.

Our first question in TYI (57) was if there are non-intuitive norms. We further asked which norms are intuitive.

(In the question I used “nice” instead of “intuitive” and did not mention the term “geometric median”.)

The answer is given by a recent theorem of Shay Moran, Alexander Shlimovich, and Amir Yehudayoff in their paper: Intuitive norms are Euclidean:

Answer to TYI (57): In the plane all norms are intuitive; in dimensions 3 and more, only Euclidean norms are.