# A new $\ell_p$-metric on the hyperspace of finite sets?

Let $(X,d)$ be a metric space and $Fin(X)$ be the family of all non-empty finite subsets of $X$. For every $n\in\mathbb N$ the elements of the power $X^n$ are thought as functions $f:n\to X$ where $n:=\{0,\dots,n-1\}$. For such function $f$ its image $f(n)\subset X$ will be denoted by $rg(f)$.

For every $p\in[1,\infty]$ the space $X^n$ is endowed with the $\ell_p$-metric $d_p$ defined by $$d_p(f,g)=\begin{cases}\sqrt[p]{\sum_{i\in n}d(f(i),g(i))^p}& \mbox{if p<\infty;}\\ \;\;\max_{i\in n}d(f(i),g(i))&\mbox{if p=\infty.} \end{cases}$$

I am interested in the metric $d_p$ on the hyperspace $Fin(X)$, defined by the formula$$d_p(A,B):=\inf\sum_{i=0}^kd_p(f_i,g_i)$$ where the infimum is taken over all chains $(f_0,g_0),\dots,(f_k,g_k)\in\bigoplus_{n\in\mathbb N}X^n\times X^n$ such that $A=rg(f_0)$, $B=rg(g_k)$ and $rg(g_i)=rg(f_{i+1})$ for all $i<k$.

The metric $d_p$ can be equivalently defined as the largest metric on $Fin(X)$ such that for every $n\in\mathbb N$ the map $X^n\to Fin(X)$, $(x_1,\dots,x_n)\mapsto\{x_1,\dots,x_n\}$, is non-expanding with respect to the $\ell_p$-metric on $X^n$.

It can be shown that the distance $d_\infty$ on $Fin(X)$ coincides with the well-known Hausdorff metric. I am interested in the metrics $d_p$ on $Fin(X)$ for $p<\infty$, especially in the metric $d_1$ on $Fin(X)$.

The distance $d_1$ can have applications in economics as it represent the cost of transportation of goods whose mass is negligible comparing to the mass of the transporting car.

For the metric $d_1$ many natural problems appear. In particular:

Problem. Find an (efficient) algorithm for calculating the distance $d_1(A,B)$ between two finite subsets $A,B$ of $\mathbb R^n$ (for $n=1$ this problem has been resolved here).

Have such problems been studied in mathematical or economical literature?

Remark 1. In the simplest case of the 2-element set $\{a,b\}$ and a 1-element set $\{c\}$ in the plane the distance $d_1(\{a,b\},\{c\})=\|a-t\|+\|b-t\|+\|c-t\|$ where $t$ is the Fermat-Toricelli point of the triangle $\{a,b,c\}$, and $\|\cdot\|$ is the standard Euclidean norm on the plane.

Remark 2. It seems that for arbitrary finite sets $A,B$ in the plane the distance $d_1(A,B)$ is equal to the smallest total length of edges of a graph $\Gamma\subset\mathbb R^2$ whose any connected component intersects both sets $A$ and $B$.
The problem of finding such graph $\Gamma$ is related to the classical Steiner tree problem which is known to be difficult (at least, NP-hard), so the problem of calculating the distance $d_1$ on $Fin(\mathbb R^2)$ is also hard. But maybe for the real line or for the Urysohn universal metric space $\mathbb U$ this problem is computationally more simple? In the latter case the distance $d_1$ between two finite subsets of $A,B$ of $\mathbb U$ depends only on the restriction of the metric to $A\cup B$ and hence depends on finite number of real parameters; so, in principle, is computable.

Remark 3. It seems that the completion of the metric space $(Fin(\mathbb R),d_1)$ can be identified with the space of all compact subsets of zero Lebesgue measure on the real line.

• Without any closer look: May be related to Gromov-Hausdorff or Hausdorff-Wasserstein distances. – Dirk Jul 31 '17 at 20:30
• @Dirk Hausdorff-Wasserstein metric computes the distance between measures living on given closed sets, but in the definition of the metric $d^p_{FX}$ no measures are involved. The Gromov-Hausdorff metric is a kind of Haudorff, so $d^\infty$-metric. – Taras Banakh Jul 31 '17 at 21:02
• @Wlod-AA You are right. This is a typo. I mean the summation in the definition of the metric $d_p$ on $Fin(X)$ should start from 0 (or the numbering of chain from 1). The essence of the metric $d_p$ is the following: it is the largest metric on $Fin(X)$ such that for every $n\in\mathbb N$ the map $X^n\to F(X)$, $(x_1,\dots,x_n)\mapsto \{x_1,\dots,x_n\}$ is non-expanding. I will write this equivalent description of $d_p$ in the body. – Taras Banakh Aug 1 '17 at 4:24
• @user64494 Definition cannot be incorrect:) A proof can be incorrect. Besides, the equality $n=\{0,\dots,n-1\}$ is the standard understanding of ordinals in the Set Theory. An ordinal is the set of all smaller ordinals and a natural number is just a finite ordinal. – Taras Banakh Aug 1 '17 at 5:32
• Thank you, @Wlod AA, you know how to make good compliments! – Taras Banakh Aug 1 '17 at 13:45