9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Without any closer look: May be related to Gromov-Hausdorff or Hausdorff-Wasserstein distances. $\endgroup$ – Dirk Jul 31 '17 at 20:30
  • $\begingroup$ @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. $\endgroup$ – Taras Banakh Jul 31 '17 at 21:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Taras Banakh Aug 1 '17 at 4:24
  • 2
    $\begingroup$ @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. $\endgroup$ – Taras Banakh Aug 1 '17 at 5:32
  • 1
    $\begingroup$ Thank you, @Wlod AA, you know how to make good compliments! $\endgroup$ – Taras Banakh Aug 1 '17 at 13:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.