Diversities and the Generalized Circumradius

David Bryant Department of Mathematics and Statistics, University of Otago, Dunedin, New Zealand. email: [email protected] phone: +64 34797889. (Corresponding author) Katharina T. Huber School of Computing Sciences, University of East Anglia, NR4 7TJ, Norwich, United Kingdom Vincent Moulton School of Computing Sciences, University of East Anglia, NR4 7TJ, Norwich, United Kingdom Paul F. Tupper Department of Mathematics, Simon Fraser University, Burnaby, British Columbia V5A 1S6, Canada

Abstract

The generalized circumradius of a set of points $A\subseteq\mathbb{R}^{d}$ with respect to a convex body $K$ equals the minimum value of $\lambda\geq 0$ such that a translate of $\lambda K$ contains $A$ . Each choice of $K$ gives a different function on the set of bounded subsets of $\mathbb{R}^{d}$ ; we characterize which functions can arise in this way. Our characterization draws on the theory of diversities, a recently introduced generalization of metrics from functions on pairs to functions on finite subsets. We additionally investigate functions which arise by restricting the generalized circumradius to a finite subset of $\mathbb{R}^{d}$ . We obtain elegant characterizations in the case that $K$ is a simplex or parallelotope.

The circumradius of a set of points in the plane is the radius of the smallest circle containing them. The concept is key to optimal containment and facility location problems, including a classic problem studied by Sylvester [21, 32], since the center of the smallest enclosing circle minimizes the maximum distance to any of the points.

The generalized circumradius replaces the plane with $\mathbb{R}^{d}$ and the circle or ball with a general convex body, that is a compact, convex set with non-empty interior. For a convex body $K$ in $\mathbb{R}^{d}$ and bounded $A\subseteq\mathbb{R}^{d}$ we say that the generalized circumradius of $A$ with respect to $K$ is

R(A,K)=\inf\{\lambda\geq 0:A\subseteq\lambda K+x\mbox{ for some $x\in\mathbb{R}^{d}$}\}.

In other words, $R(A,K)$ equals the minimal amount that $K$ must be scaled so that a translate covers $A$ (see Fig. 1). The set $K$ is called the kernel. See [2, 3, 16, 22] for properties and inequalities related to the generalized circumradius and [4, 18, 17, 19] for computational results.

Refer to caption — Figure 1: An example of the generalized circumradius. In this example $R(\{a,b,d,g,k\},K)=2$ since $2K$ is the smallest scaled version of $K$ which can be translated to cover $\{a,b,d,g,k\}$ . Similarly, $R(\{c,e,f\},K)=0.6$ , since $0.6K$ is the smallest scaled version of $K$ which can be translated to cover $\{c,e,f\}$ , and $R(\{h,i\},K)=1$ .

Our motivation for studying the generalized circumradius comes from connections with diversity theory. A (mathematical) diversity is an extension of the idea of a metric space. Instead of assigning values just to pairs of objects, a diversity assigns values to all finite sets of objects. More formally, a diversity is a pair $(X,\delta)$ where $X$ is a set and $\delta$ a function from finite subsets of $X$ to $\mathbb{R}_{\geq 0}$ such that, for $A,B,C$ finite,

(D1)

$\delta(A)=0$ if and only if $|A|\leq 1$ .
(D2)

If $B\neq\emptyset$ then $\delta(A\cup C)\leq\delta(A\cup B)+\delta(B\cup C)$ .

Diversities were introduced in [9]. A consequence of (D1) and (D2) is that diversities are monotonic, that is, if $A\subseteq B$ then $\delta(A)\leq\delta(B)$ . Furthermore, $\delta$ restricted to pairs satisfies the definition of a metric; we call this the metric induced by $(X,\delta)$ . We say that a diversity $(X,\delta)$ is finite if $X$ is finite. Note that on occasion we use the term ‘diversity’ to refer to the function $\delta$ rather than the pair $(X,\delta)$ .

Many well-known functions on sets are diversities. Examples include

1.

The diameter of a set
2.

The length of a shortest Steiner tree connecting a set
3.

The mean width of a set
4.

The length of the shortest traveling salesman tour through a set
5.

The $L_{1}$ diversity (in $\mathbb{R}^{d}$ )

$\delta(A)=\delta_{1}(A)=\sum_{i=1}^{d}\max\{|a_{i}-a^{\prime}_{i}|:a,a^{\prime}\in A\}$
6.

The circumradius of a set.

We show that the generalized circumradius is also a diversity:

Theorem 0.

Let $K$ be a convex body in $\mathbb{R}^{d}$ . If we define $\delta(A)=R(A,K)$ for all finite $A$ then $(\mathbb{R}^{d},\delta)$ is a diversity.

In reference to the concept of a Minkowski norm we say that a diversity $(\mathbb{R}^{d},\delta)$ is a Minkowski diversity if there is a convex body $K$ such that $\delta(A)=R(A,K)$ for all finite $A\subset\mathbb{R}^{d}$ .

Theorem 5 connects the generalized circumradius to a growing and varied literature on diversity theory. The first diversity paper [9] described diversity analogs to the metric tight span and metric hyperconvexity, leading to new results in analysis and fixed point theory [23, 26, 27]. It was shown in [10] that results of [25] and others on embedding of finite metrics in $L_{1}$ can be extended to diversities, with potential algorithmic gains. There is a direct analog of the Urysohn metric space [7] for diversities and work on diversity theory within model theory [8, 20], lattice theory [6, 33], image analysis [15], machine learning [24] and phylogenetics [5, 9, 30, 31].

In this paper we are mainly concerned with characterizations and embeddings for Minkowski diversities—what characterizes these diversities and which finite diversities can be embedded into a Minkowski diversity. Such embeddings (possibly with distortion) should in future provide valuable graphical representations of diversities in addition to algorithmic and computational tools.

Regarding characterization we prove the following result. A real-valued function $f$ on subsets of $\mathbb{R}^{d}$ is said to be sublinear if

	$\displaystyle f(A+B)$	$\displaystyle\leq f(A)+f(B)$	for all $A,B$ ,
	$\displaystyle f(\lambda A)$	$\displaystyle=\lambda f(A)$	$\displaystyle\mbox{for all $A$ and $\lambda\geq 0$},$

where $A+B$ denotes the Minkowski sum.

Theorem 0.

Let $(\mathbb{R}^{d},\delta)$ be a diversity. Then $\delta$ is a Minkowski diversity if and only if $\delta$ is sublinear and for all finite $A,B$ there are $a,b\in\mathbb{R}^{d}$ such that

\delta((A+a)\cup(B+b))\leq\max\{\delta(A),\delta(B)\}.

We also show that the last result extends beyond diversities to functions defined on bounded subsets of $\mathbb{R}^{d}$ .

Theorem 0.

Let $f$ be a function on bounded subsets of $\mathbb{R}^{d}$ . Then there is a convex body $K$ such that $f(A)=R(A,K)$ for all bounded $A$ if and only if $f$ is sublinear, monotonic, and $f$ restricted to finite subsets is a Minkowski diversity.

Having characterized which diversities on $\mathbb{R}^{d}$ are Minkowski diversities, we turn to the more difficult problem of characterizing which diversities can be isometrically embedded into Minkowski diversities. An isometric embedding of a diversity $(X,\delta_{1})$ into a diversity $(\mathbb{R}^{d},\delta_{2})$ is a map $\phi:X\rightarrow\mathbb{R}^{d}$ such that $\delta_{1}(A)=\delta_{2}(\phi(A))$ for all finite $A\subseteq X$ . If there is an isometric embedding from a diversity $(X,\delta_{1})$ into a Minkowski diversity $(\mathbb{R}^{d},\delta_{K})$ for some $d$ and some convex body $K\subseteq\mathbb{R}^{d}$ then we say that $(X,\delta_{1})$ is Minkowski-embeddable.

We provide a complete characterization of Minkowski-embeddability for diversities which are finite and symmetric, meaning that the diversity of a set is determined by a function of its cardinality.

Theorem 0.

Let $(X,\delta)$ be a finite symmetric diversity. Then $(X,\delta)$ is Minkowski-embeddable if and only if

\frac{\delta(A\setminus\{a\})}{\delta(A)}\geq\frac{|A|-2}{|A|-1}

(1)

for all $A\subseteq X$ with $|A|\geq 2$ , $a\in A$ .

A consequence of the theorem is that, even though any diversity on three elements is Minkowski-embeddable, there exist diversities on four elements which are not.

We then investigate which finite diversities $(X,\delta_{1})$ can be embedded into the diversity $(\mathbb{R}^{d},\delta_{2})$ when $\delta_{2}$ is a Minkowski diversity with kernel $K$ restricted to a particular class. A diversity $(X,\delta)$ is a diameter diversity if $\delta(A)=\max\{\delta(\{a,a^{\prime}\}):a,a^{\prime}\in A\}$ for all finite $A\subseteq X$ , see [9]. The following characterization for when $K$ is a cube (or non-degenerate transform of a cube) follows from an observation of [2].

Theorem 0.

A finite diversity $(X,\delta)$ can be embedded in a Minkowski diversity with kernel equal to some parallelotope if and only if $(X,\delta)$ is a diameter diversity.

The case when $K$ is a simplex is more complex. We say that a finite diversity $(X,\delta)$ is of negative type if

\sum_{A\neq\emptyset}\sum_{B\neq\emptyset}x_{A}x_{B}\delta(A\cup B)\leq 0

for all zero-sum vectors $x$ indexed by non-empty subsets of $X$ . Diversities of negative type are analogous to metrics of negative type, and several of the properties of metrics of negative type extend to diversities of negative type, see [35]. For negative-type diversities we prove the following characterization.

Theorem 0.

A finite diversity $(X,\delta)$ can be embedded in a Minkowski diversity with kernel equal to some simplex if and only if $(X,\delta)$ has negative type.

Significantly, the set of diversities with negative type is quite large, with the same dimension as the set of diversities on $X$ . The result shows that the class of Minkowski-embeddable diversities is even larger, potentially opening up possibilities for quite general theoretical and algorithmic results.

1 The generalized circumradius

In this section we collect together a number of fundamental results about the generalized circumradius. We begin with several observations from [21] (Proposition 3.2). Let $\mathrm{conv}(A)$ denote the convex hull of $A$ .

Proposition 1.

Let $A,A^{\prime},B$ be bounded subsets of $\mathbb{R}^{d}$ , let $K,K^{\prime}$ be convex bodies in $\mathbb{R}^{d}$ . Then

(a)

If $A\subseteq A^{\prime}$ and $K^{\prime}\subseteq K$ then $R(A,K)\leq R(A^{\prime},K^{\prime})$ .
(b)

If $\mathrm{conv}(A)=\mathrm{conv}(A^{\prime})$ then $R(A,K)=R(A^{\prime},K)$ .
(c)

$R(A+B,K)\leq R(A,K)+R(B,K)$ with equality if $B=\alpha K$ for some $\alpha\geq 0$ .
(d)

$R(A+x,K+y)=R(A,K)$ for all $x,y\in\mathbb{R}^{d}$ .
(e)

$R(\alpha A,\beta K)=(\alpha/\beta)R(A,K)$ for $\alpha,\beta>0$ .

An indirect consequence of Helly’s theorem (see e.g. [13], Section 6.2) is that for bounded $A\subseteq\mathbb{R}^{d}$ and a convex body $K$ we can find a small subset $A^{\prime}\subseteq A$ such that $|A^{\prime}|\leq d+1$ and $R(A^{\prime},K)=R(A,K)$ . The following more general result forms one part of Theorem 1.2 in [2].

Proposition 2.

Suppose that $A\subset\mathbb{R}^{d}$ is bounded and $K$ is a convex body. For all $\epsilon\geq 0$ there exists $A^{\prime}\subseteq A$ such that $|A^{\prime}|\leq\left\lceil\frac{d}{1+\epsilon}\right\rceil+1$ and

R(A^{\prime},K)\leq R(A,K)\leq(1+\epsilon)R(A^{\prime},K).

Note that for particular choices of $K$ there can be much smaller bounds on $|A^{\prime}|$ . For example, when $K$ is the Euclidean ball in $\mathbb{R}^{d}$ we have for all bounded $A\subset\mathbb{R}^{d}$ and $\epsilon>0$ that there is a subset $A^{\prime}\subseteq A$ such that $R(A,K)\leq(1+\epsilon)R(A^{\prime},K)$ and

|A^{\prime}|\leq\left\lceil\frac{1}{2\epsilon+\epsilon^{2}}\right\rceil+1.

This bound is independent of the dimension $d$ .

We will make use of the following general property for Minkowski addition which is established during the proof of Theorem 4.1 in [2]. Let $A\subseteq\mathbb{R}^{d}$ be any set with cardinality $k+1$ , $k\geq 2$ , and zero sum. Then

A\subseteq\frac{k}{(k+1)(k-1)}\sum_{a\in A}\mathrm{conv}(A\setminus\{a\}).

Combining this observation with Proposition 1 (d), (b) and (c) we have

Proposition 3.

Suppose $A\subset\mathbb{R}^{d}$ , $|A|=k+1$ and $K$ is a convex body. Then

R(A,K)\leq\frac{k}{(k+1)(k-1)}\sum_{a\in A}R(A\setminus\{a\},K).

For $C\subseteq\mathbb{R}^{p}\times\mathbb{R}^{q}$ we define the two projection operators

	$\displaystyle\pi_{1}(C)$	$\displaystyle=\{c_{1}\in\mathbb{R}^{p}:(c_{1},c_{2})\in C\mbox{ for some $c_{2}$}\}$
	$\displaystyle\pi_{2}(C)$	$\displaystyle=\{c_{2}\in\mathbb{R}^{q}:(c_{1},c_{2})\in C\mbox{ for some $c_{1}$}\}.$

The following result will be useful for questions regarding embeddings.

Proposition 4.

Let $A$ be a bounded subset of $\mathbb{R}^{p}\times\mathbb{R}^{q}$ . If $B$ and $C$ are convex bodies in $\mathbb{R}^{p}$ and $\mathbb{R}^{q}$ respectively, then

R(A,B\times C)=\max\{R(\pi_{1}(A),B),R(\pi_{2}(A),C)\}.

Proof.

Suppose $\lambda=R(A,B\times C)$ and that

A+(a_{1},a_{2})\subseteq\lambda(B\times C).

Applying $\pi_{1}$ and $\pi_{2}$ to both sides gives

\pi_{1}(A)+a_{1}\subseteq\lambda B

and

\pi_{2}(A)+a_{2}\subseteq\lambda C.

Hence $\max\{R(\pi_{1}(A),B),R(\pi_{2}(A),C)\}\leq R(A,B\times C)$ .

Conversely, if $\lambda=\max\{R(\pi_{1}(A),B),R(\pi_{2}(A),C)\}$ , then there are $a_{1},a_{2}$ such that

	$\displaystyle\pi_{1}(A)+a_{1}$	$\displaystyle\subseteq\lambda B$
	$\displaystyle\pi_{2}(A)+a_{2}$	$\displaystyle\subseteq\lambda C.$

We then have

	$\displaystyle A+(a_{1},a_{2})$	$\displaystyle\subseteq\pi_{1}(A)\times\pi_{2}(A)+(a_{1},a_{2})$
		$\displaystyle=(\pi_{1}(A)+a_{1})\times(\pi_{2}(A)+a_{2})$
		$\displaystyle\subseteq\lambda(B\times C)$

so that $R(A,B\times C)\leq\max\{R(\pi_{1}(A),B),R(\pi_{2}(A),C)\}$ . ∎

2 Characterization of Minkowski diversities

We begin this section by proving the first main result connecting the theory of generalized circumradii with diversity theory.

Theorem 5.

Let $K$ be a convex body in $\mathbb{R}^{d}$ . If $\delta(A)=R(A,K)$ for all finite $A$ , then $(\mathbb{R}^{d},\delta)$ is a diversity.

Proof.

Clearly $\delta(A)\geq 0$ for all $A$ and $\delta(A)=R(A,K)=0$ if and only if $|A|\leq 1$ . Hence (D1) holds. By Proposition 1 (a), $R(A,K)$ is monotonic in $A$ .

Suppose $A$ and $B$ are finite subsets of $\mathbb{R}^{d}$ and $x\in A\cap B$ . Then $(A-x)=(A-x)+0\subseteq(A-x)+(B-x)$ and $(B-x)=0+(B-x)\subseteq(A-x)+(B-x)$ . Hence

(A-x)\cup(B-x)\subseteq(A-x)+(B-x),

and so by Proposition 1 (d) and (c),

	$\displaystyle\delta(A\cup B)$	$\displaystyle=\delta((A\cup B)-x)$
		$\displaystyle=\delta((A-x)\cup(B-x))$
		$\displaystyle\leq\delta(A-x)+\delta(B-x)$
		$\displaystyle=\delta(A)+\delta(B).$

This fact, together with monotonicity, implies the diversity triangle inequality (D2).

∎

In the rest of this section we focus on characterizing which diversities on $\mathbb{R}^{d}$ can be obtained in this way (Theorem 8).

Let $\mathfrak{B}$ denote the Euclidean unit ball in $\mathbb{R}^{d}$ . The Hausdorff distance on (bounded) subsets of $\mathbb{R}^{d}$ is given by

d_{H}(A,B)=\inf\{\lambda:A\subseteq B+\lambda\mathfrak{B}\mbox{ and }B\subseteq A+\lambda\mathfrak{B}\},

see [29]. We note that $d_{H}$ becomes a metric when restricted to compact sets.

A diversity $(\mathbb{R}^{d},\delta)$ is sublinear if $\delta$ is a sublinear function, $\delta(A+B)\leq\delta(A)+\delta(B)$ and $\delta(\lambda A)=\lambda\delta(A)$ for all finite $A,B$ and non-negative $\lambda$ . Note that finite sublinear diversities are closely related to set-norms [12, Def. 2.1]. The $L_{1}$ diversity $(\mathbb{R}^{d},\delta_{1})$ , as introduced earlier, is an example of a sublinear diversity. Here,

\delta_{1}(A)=\sum_{i=1}^{d}\max\{|a_{i}-a^{\prime}_{i}|:a,a^{\prime}\in A\},

and $\delta_{1}$ is sublinear since, given $\lambda\geq 0$ and finite subsets $A,B\subseteq\mathbb{R}^{d}$ we have

	$\displaystyle\delta_{1}(\lambda A)$	$\displaystyle=\sum_{i=1}^{d}\max\{\|\lambda a_{i}-\lambda a^{\prime}_{i}\|:a,a^{\prime}\in A\}$
		$\displaystyle=\lambda\delta_{1}(A),$
and
	$\displaystyle\delta_{1}(A+B)$	$\displaystyle=\sum_{i=1}^{d}\max\{\|a_{i}+b_{i}-a^{\prime}_{i}-b^{\prime}_{i}\|:a,a^{\prime}\in A,b,b^{\prime}\in B\}$
		$\displaystyle\leq\sum_{i=1}^{d}\max\{\|a_{i}-a^{\prime}_{i}\|:a,a^{\prime}\in A\}+\max\{\|b_{i}-b^{\prime}_{i}\|:b,b^{\prime}\in B\}$
		$\displaystyle=\delta_{1}(A)+\delta_{1}(B).$

Sublinearity has several important consequences for diversities.

Proposition 6.

Let $(\mathbb{R}^{d},\delta)$ be a sublinear diversity. Then

(a)

$\delta$ is translation invariant: $\delta(A+x)=\delta(A)$ for all $x$ .
(b)

$\delta$ is determined by the convex hull: if $A,B$ finite in $\mathbb{R}^{d}$ and $\mathrm{conv}(A)=\mathrm{conv}(B)$ , then $\delta(A)=\delta(B)$ .
(c)

$\delta$ is Lipschitz continuous with respect to the Hausdorff metric.

Proof.

(a) By (D1) and sublinearity, we have

	$\displaystyle\delta(A+x)$	$\displaystyle\leq\delta(A)+\delta(\{x\})=\delta(A),\mbox{ and }$
	$\displaystyle\delta(A)$	$\displaystyle\leq\delta(A+x)+\delta(\{-x\})=\delta(A+x).$

(b) Let $B^{\prime}\subseteq B$ be a maximal subset of $B$ such that $\delta(A\cup B^{\prime})=\delta(A)$ . Suppose that there is $b\in B\setminus B^{\prime}$ . As $b\in\mathrm{conv}(B)=\mathrm{conv}(A)$ there are non-negative $\{\lambda_{a}\}_{a\in A}$ with unit sum such that

b=\sum_{a}\lambda_{a}a

and hence

b\in\sum_{a}\lambda_{a}A.

A\cup B^{\prime}\subseteq\sum_{a}\lambda_{a}(A\cup B^{\prime})

we have

\delta(A\cup B^{\prime}\cup\{b\})\leq\delta\Big{(}\sum_{a}\lambda_{a}(A\cup B^{\prime})\Big{)}\leq\sum_{a}\lambda_{a}\delta(A\cup B^{\prime})=\delta(A\cup B^{\prime})=\delta(A).

This contradicts the choice of $B^{\prime}$ . Hence $B^{\prime}=B$ and $\delta(A\cup B)=\delta(A)$ . Exchanging $A$ and $B$ in this argument gives $\delta(A\cup B)=\delta(B)$ . Hence $\delta(A)=\delta(B)$ .
(c) Let $V$ denote any finite set with convex hull $\mathrm{conv}(V)$ containing the unit ball $\mathfrak{B}$ . One example is $V=\{-1,1\}^{d}$ . Let $\kappa=\delta(V)$ and suppose that $d_{H}(A,B)=\lambda$ . From the definition of $d_{H}$ we have $A\subseteq B+\lambda\mathfrak{B}$ and $B\subseteq A+\lambda\mathfrak{B}$ so there are finite sets $A^{\prime},B^{\prime}\subseteq\mathfrak{B}$ such that

A\subseteq B+\lambda A^{\prime}\mbox{ and }B\subseteq A+\lambda B^{\prime}.

As $\mathfrak{B}\subseteq\mathrm{conv}(V)$ , we have $\mathrm{conv}(A^{\prime}\cup V)\!=\!\mathrm{conv}(B^{\prime}\cup V)\!=\!\mathrm{conv}(V)$ . By sublinearity, monotonicity of $\delta$ and part (b) we therefore have

\delta(A)\leq\delta(B)+\lambda\delta(V)\mbox{ and }\delta(B)\leq\delta(A)+\lambda\delta(V)

giving $|\delta(A)-\delta(B)|\leq\kappa d_{H}(A,B)$ . ∎

Our next theorem gives a complete characterization of Minkowski diversities. A key idea in the proof of the theorem is that we can extend a sublinear diversity $(\mathbb{R}^{d},\delta)$ to a function on convex bodies in $\mathbb{R}^{d}$ . More specifically, given a sublinear diversity $\delta$ , define the function $\tilde{\delta}$ on the set of convex bodies in $\mathbb{R}^{d}$ by setting

\tilde{\delta}(P)=\delta(\mathrm{Vert}(P))

for all polytopes $P$ with vertex set $\mathrm{Vert}(P)$ and

\tilde{\delta}(K)=\ \lim_{n\rightarrow\infty}\tilde{\delta}(P_{n})

for any convex body $K$ and sequence $P_{1},P_{2},\ldots$ of polytopes converging under the Hausdorff metric to $K$ .

Lemma 7.

Given a sublinear diversity $\delta$ , the function $\tilde{\delta}$ is well-defined and Lipschitz continuous.

Proof.

Since $\tilde{\delta}$ is Lipschitz on the set of polytopes, it is uniformly continuous on the same set, and so can be uniquely extended to a continuous function on the closure of that set [28, Prob. 13, Ch. 4], the convex bodies. An expression for $\tilde{\delta}$ can then be obtain for convex bodies using the limits of sequences of polytopes as above, and this gives that the extension has the same Lipschitz constant. ∎

Using this observation, we now prove the main theorem for this section.

Theorem 8.

Let $(\mathbb{R}^{d},\delta)$ be a diversity. Then $(\mathbb{R}^{d},\delta)$ is a Minkowski diversity if and only if $\delta$ is sublinear and for all finite $A,B$ there are $a,b\in\mathbb{R}^{d}$ such that

\delta((A+a)\cup(B+b))\leq\max\{\delta(A),\delta(B)\}.

(2)

Proof.

Suppose that $(\mathbb{R}^{d},\delta)$ is a Minkowski diversity, so that there is a convex body $K\subseteq\mathbb{R}^{d}$ such that $\delta(A)=R(A,K)$ for all finite $A\subseteq\mathbb{R}^{d}$ . Sublinearity is given by Proposition 1 parts (c) and (e). Given finite $A$ and $B$ , there are $a,b\in\mathbb{R}^{d}$ such that $A\subseteq\delta(A)K-a$ and $B\subseteq\delta(B)K-b$ . Hence

(A+a)\cup(B+b)\subseteq\max\{\delta(A),\delta(B)\}K

and

	$\displaystyle\delta((A+a)\cup(B+b))$	$\displaystyle=R((A+a)\cup(B+b),K)$
		$\displaystyle\leq R(\max\{\delta(A),\delta(B)\}K,K)$
		$\displaystyle=\max\{\delta(A),\delta(B)\}R(K,K)$
		$\displaystyle=\max\{\delta(A),\delta(B)\}.$

Now suppose that $(\mathbb{R}^{d},\delta)$ is sublinear and satisfies (2) for all finite $A,B$ . Let

\rho=\max\left\{\frac{\|x\|}{\delta(\{0,x\})}:x\neq 0\right\}=\max\left\{\frac{1}{\delta(\{0,x\})}:\|x\|=1\right\}.

Then $0<\rho<\infty$ and $\|x-y\|\leq\rho\delta(\{x,y\})$ for all $x,y$ . (Here and below we use $\|\cdot\|$ to denote Euclidean norm).

We show that for any convex bodies $L,K\subseteq\mathbb{R}^{d}$ and the function $\tilde{\delta}$ in Lemma 7 there is some $x\in\mathbb{R}^{d}$ such that

\tilde{\delta}(\mathrm{conv}(K\cup(L+x)))\leq\max\{\tilde{\delta}(K),\tilde{\delta}(L)\}.

(3)

Suppose that $K_{1},K_{2},\ldots$ is a sequence of finite subsets of $K$ such that $\mathrm{conv}(K_{n})\rightarrow K$ and $L_{1},L_{2},\ldots$ is a sequence of finite subsets of $L$ such that $\mathrm{conv}(L_{n})\rightarrow L$ . Applying (2) and translation invariance of $\delta$ we have that for each $n\in\mathbb{N}$ there is an $x_{n}\in\mathbb{R}^{d}$ such that

\delta(K_{n}\cup(L_{n}+x_{n}))\leq\max\{\delta(K_{n}),\delta(L_{n})\}.

Hence, for all $n$ ,

\tilde{\delta}(\mathrm{conv}(K_{n}\cup(L_{n}+x_{n})))\leq\max\{\tilde{\delta}(\mathrm{conv}(K_{n})),\tilde{\delta}(\mathrm{conv}(L_{n}))\}.

(4)

We show that the sequence $x_{n}$ has a convergent subsequence. First note that since $K$ and $L$ are bounded, convergence of $\mathrm{conv}(K_{n})$ and $\mathrm{conv}(L_{n})$ to them in the Hausdorff metric implies that the union of all these sets is bounded, and hence the sequence $\max\{\delta(K_{n}),\delta(L_{n})\}$ is bounded. Choose $k_{n}\in K_{n}$ and $\ell_{n}\in L_{n}$ for each $n$ , which are then bounded over all $n$ . We then have

\|x_{n}-(k_{n}-\ell_{n})\|=\|(x_{n}+\ell_{n})-k_{n}\|\leq\rho\delta(K_{n}\cup(L_{n}+x_{n}))\leq\max\{\delta(K_{n}),\delta(L_{n})\}.

So the set $\{x_{1},x_{2},x_{3},\ldots\}$ is bounded. Let $x_{i_{1}},x_{i_{2}},\ldots$ be a convergence subsequence and let $x\in\mathbb{R}^{d}$ be its limit.

Since $\mathrm{conv}(L_{n})\rightarrow L$ and $x_{n}\rightarrow x$ , $\mathrm{conv}(L_{n}+x_{n})\rightarrow L+x$ . So, $\mathrm{conv}(K_{n})\cup\mathrm{conv}(L_{n}+x_{n})\rightarrow K\cup(L+x)$ and

\mathrm{conv}(K_{n}\cup(L_{n}+x_{n}))=\mathrm{conv}(\mathrm{conv}(K_{n})\cup\mathrm{conv}(L_{n}+x_{n}))\rightarrow\mathrm{conv}(K\cup(L+x)).

Taking the limit as $n\rightarrow\infty$ of (4) and using the continuity of $\tilde{\delta}$ gives (3) which proves the claim.

Let $\mathfrak{C}$ denote the set of convex bodies

\mathfrak{C}=\{A\subseteq\mathbb{R}^{d}:\tilde{\delta}(A)\leq 1\}.

The set $\mathfrak{C}$ is closed under the Hausdorff metric and both volume and $\tilde{\delta}$ are continuous with respect to the Hausdorff metric [29, Sec 1.8]. It follows that there is some $K\in\mathfrak{C}$ such that the volume of $K$ is at least as large as any other element in $\mathfrak{C}$ . The convex body $K$ is necessarily inclusion-maximum: if $K$ was a proper subset of some $K^{\prime}\in\mathfrak{C}$ then the volume of $K^{\prime}$ would be strictly greater than the volume of $K$ .

We claim that $R(A,K)=1$ for all finite $A$ such that $\delta(A)=1$ .

Let $A$ be finite with $\delta(A)=1$ . By (3) there is $x\in\mathbb{R}^{d}$ such that

\tilde{\delta}(\mathrm{conv}(K\cup(\mathrm{conv}(A)+x)))\leq\max\{\tilde{\delta}(K),\tilde{\delta}(\mathrm{conv}(A))\}=1.

We therefore have $\mathrm{conv}(K\cup(\mathrm{conv}(A)+x))\in\mathfrak{C}$ . As $K$ is set inclusion-maximum in $\mathfrak{C}$ and $K\subseteq\mathrm{conv}(K\cup(\mathrm{conv}(A)+x))$ we have

K=\mathrm{conv}(K\cup(\mathrm{conv}(A)+x))

and so $A+x\subseteq K$ and $R(A,K)\leq 1$ . On the other hand, if there is some $\lambda\geq 0$ and $z\in\mathbb{R}^{d}$ such that $A\subseteq\lambda K+z$ then

\delta(A)=\tilde{\delta}(\mathrm{conv}(A))\leq\tilde{\delta}(\lambda K+z)=\lambda\tilde{\delta}(K)=\lambda,

showing that $R(A,K)\geq 1$ . Hence $R(A,K)=1$ , as claimed.

It follows that $\delta(A)=R(A,K)$ when $\delta(A)=1$ .

More generally, suppose $\delta(A)=d$ . The case $d=0$ is straightforward, as then $|A|\leq 1$ . If $d>0$ then, by sublinearity, $\delta(A)=d\delta(\frac{1}{d}A)=dR(\frac{1}{d}A,K)=R(A,K)$ . ∎

We note that there are diversities on $\mathbb{R}^{d}$ which are sublinear, but do not satisfy property (2) in Theorem 8 (and are hence not Minkowski diversities). For example, consider the $L_{1}$ diversity in the plane $(\mathbb{R}^{2},\delta_{1})$ . We saw above that $L_{1}$ diversities are sublinear but if

A=\left\{\left[\begin{matrix}0\\ 0\end{matrix}\right],\left[\begin{matrix}1\\ 0\end{matrix}\right]\right\}\mbox{ and }B=\left\{\left[\begin{matrix}0\\ 0\end{matrix}\right],\left[\begin{matrix}0\\ 1\end{matrix}\right]\right\}

then for any $a,b\in\mathbb{R}^{2}$ we have

\delta_{1}((A+a)\cup(B+b))\geq 2>1=\max\{\delta_{1}(A),\delta_{1}(B)\}.

The set of diversities on $\mathbb{R}^{d}$ , and indeed the the set of sublinear diversities on $\mathbb{R}^{d}$ , are both convex. Condition (2) in Theorem 8 suggests that the set of Minkowski diversities on $\mathbb{R}^{d}$ is not convex, as we now confirm.

Proposition 9.

The set of Minkowski diversities on $\mathbb{R}^{d}$ , $d\geq 2$ , is not convex.

Proof.

We first establish this for $d=2$ . Let

	$\displaystyle A$	$\displaystyle=\left\{\left[\begin{matrix}1\\ 0\end{matrix}\right],\left[\begin{matrix}0\\ 1\end{matrix}\right],\left[\begin{matrix}1\\ 1\end{matrix}\right]\right\},$
	$\displaystyle B$	$\displaystyle=\left\{\left[\begin{matrix}1\\ 0\end{matrix}\right],\left[\begin{matrix}2\\ 0\end{matrix}\right],\left[\begin{matrix}1\\ 1\end{matrix}\right]\right\},$
	$\displaystyle B^{\prime}$	$\displaystyle=\left\{\left[\begin{matrix}0\\ 1\end{matrix}\right],\left[\begin{matrix}1\\ 1\end{matrix}\right],\left[\begin{matrix}0\\ 2\end{matrix}\right]\right\}.$

Let $K=\mathrm{conv}(A\cup B)$ and $K^{\prime}=\mathrm{conv}(A\cup B^{\prime})$ . Let $(X,\delta)$ be the diversity on $\mathbb{R}^{2}$ given by $\delta(Y)=\mbox{$\frac{1}{2}$}R(Y,K)+\mbox{$\frac{1}{2}$}R(Y,K^{\prime})$ . We will show that for all $a,b\in\mathbb{R}^{2}$

\delta((A+a)\cup(B+b))>\max\{\delta(A),\delta(B)\},

from which it follows by Theorem 8 that $(X,\delta)$ is not a Minkowski diversity.

First note that since $\delta$ is translation invariant, we can assume $a=0$ . Now, note that

R(A,K)=R(A,K^{\prime})=R(B,K)=R(B,K^{\prime})=1

so that

\max\{\delta(A),\delta(B)\}=1.

If $b=0$ then $R(A\cup(B+b),K)=1$ , otherwise $R(A\cup(B+b),K)>1$ . If $b=\left[\begin{matrix}-1\\ 1\end{matrix}\right]$ then $R(A\cup(B+b),K^{\prime})=1$ , otherwise $R(A\cup(B+b),K^{\prime})>1$ . Hence we have

\delta((A+a)\cup(B+b))=\mbox{$\frac{1}{2}$}R(A\cup(B+b),K)+\mbox{$\frac{1}{2}$}R(A\cup(B+b),K^{\prime})>1

even though $\max\{\delta(A),\delta(B)\}=1$ .

For $d>2$ , in the above argument we replace $K$ and $K^{\prime}$ with their product with the unit hypercube in $\mathbb{R}^{d-2}$ , and append $d-2$ zeros to the elements in $A$ and $B$ and to $x$ . ∎

3 Characterizing the general circumradius

In this section, we characterize functions $f$ for which there is a convex body $K$ such that $f(A)=R(A,K)$ for all bounded $A$ , noting that in the previous section we only considered finite $A$ . The main idea behind the proof is to show that a sublinear, monotonic function is Hausdorff continuous, after which the result follows almost immediately from Theorem 8.

Lemma 10.

Let $f$ be a sublinear, monotonic function on bounded subsets of $\mathbb{R}^{d}$ . Then $f$ is Hausdorff continuous.

Proof.

Let $\mathfrak{B}$ denote the Euclidean unit ball in $\mathbb{R}^{d}$ , let $b=f(\mathfrak{B})$ and let $\epsilon>0$ . Then for any bounded $A,B$ such that $d_{H}(A,B)\leq\frac{\epsilon}{b}$ we have

f(A)\leq f\left(B+\frac{\epsilon}{b}\mathfrak{B}\right)\leq f(B)+\epsilon

and

f(B)\leq f\left(A+\frac{\epsilon}{b}\mathfrak{B}\right)\leq f(A)+\epsilon.

∎

Theorem 11.

Proof.

Necessity follows from the arguments used for Theorem 8.

Suppose that $f$ is sublinear and monotonic, and $f$ restricted to finite subsets is a Minkowski diversity. By Lemma 10, $f$ is Hausdorff continuous. Let $A$ be a bounded subset of $\mathbb{R}^{d}$ . Then $f(\overline{A})=f(A)$ , where $\overline{A}$ denotes the topological closure of $A$ .

By Theorem 8 there is a convex body $K$ such that $f(B)=R(B,K)$ for any finite $B$ . Given any natural number $n\geq 1$ there is a finite cover of $\overline{A}$ by balls of radius $\frac{1}{n}$ . Let $A_{n}$ denote the set of centers of those balls, so that $A_{n}\rightarrow\overline{A}$ . We then have

f(A)=f(\overline{A})=\lim_{n\rightarrow\infty}f(A_{n})=\lim_{n\rightarrow\infty}R(A_{n},K)=R(A,K).

∎

4 Embedding finite diversities

In this section we consider an (isometric) embedding problem: when can a given finite diversity $(X,\delta)$ be embedded in a Minkowski diversity? There is a long history in mathematics regarding embedding of finite metrics into standard spaces. Perhaps best known is the characterization due to Cayley and Menger of when a finite metric can be embedded into Euclidean space [1, 14]. The theory of metric embeddings forms the basis of many methods for multi-dimensional scaling, an approximate low-dimensional embedding designed specifically for data reduction and representation. Approximate embeddings have proven exceptionally useful for algorithm design and approximations (e.g. [25]), work that has a direct analog in the mathematics of diversities [10].

To discuss embeddings, it is convenient to consider a slight generalization of diversities. A semimetric is a bivariate, symmetric map $d$ on $X$ that vanishes on the diagonal and satisfies the triangle inequality, but where we allow $d(x,y)=0$ even when $x\neq y$ , $x,y\in X$ (so, in particular a metric is a semimetric). Similarly, a pair $(X,\delta)$ is a semidiversity if it satisfies (D2) and the following slightly weaker version of (D1)

(D1’)

$\delta(A)=0$ if $|A|\leq 1$ .

We say that a (semi)diversity $(X,\delta)$ is Minkowski-embeddable if for some $d$ there is a map $\phi:X\rightarrow\mathbb{R}^{d}$ and a convex body $K$ in $\mathbb{R}^{d}$ such that

\delta(A)=R(\phi(A),K)

for all finite $A\subseteq X$ .

For the rest of this section we shall focus on the embedding problem for symmetric diversities, where a (semi)diversity $(X,\delta)$ is symmetric if $\delta(A)=\delta(B)$ whenever $|A|=|B|$ , $A,B\subseteq X$ , that is, the value of $\delta$ on a set depends only upon the cardinality of the set, see [11]. We shall characterize when a finite symmetric diversity is Minkowski-embeddable. As a corollary we also show that not every diversity is Minkowski-embeddable

We start with some utility results on embeddings. For convenience, for the rest of this section we shall assume that $X$ is a finite set. Note that if $(X,\delta_{1})$ and $(X,\delta_{2})$ are two semidiversities then $(X,\delta_{1}\vee\delta_{2})$ denotes the semidiversity with

(\delta_{1}\vee\delta_{2})(A)=\max\{\delta_{1}(A),\delta_{2}(A)\}

for all $A\subseteq X$ . To see that this is a semidiversity, note that for all $A,B,C$ with $B\neq\emptyset$ we have without loss of generality,

(\delta_{1}\vee\delta_{2})(A\cup C)=\delta_{1}(A\cup C)

so that

(\delta_{1}\vee\delta_{2})(A\cup C)\leq\delta_{1}(A\cup B)+\delta_{1}(B\cup C)\leq(\delta_{1}\vee\delta_{2})(A\cup B)+(\delta_{1}\vee\delta_{2})(B\cup C).

Proposition 12.

(a)

Let $(X,\delta_{1})$ and $(X,\delta_{2})$ be Minkowski-embeddable semidiversities, and $\lambda>0$ . Then both $(X,\lambda\delta_{1})$ and $(X,\delta_{1}\vee\delta_{2})$ are Minkowski-embeddable.
(b)

Suppose that $K$ is a convex body in $\mathbb{R}^{d}$ and $\phi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ is a non-degenerate affine map. Then for all $A$ we have $R(\phi(A),\phi(K))=R(A,K)$ . Hence if there is an isometric embedding from $(X,\delta)$ into $(\mathbb{R}^{d},K)$ then there is also an isometric embedding from $(X,\delta)$ into $(\mathbb{R}^{d},\phi(K))$ .
(c)

If $(X,\delta)$ is Minkowski-embeddable and $|A|=k+1$ , $k\geq 2$ , then

$\delta(A)\leq\frac{k}{(k+1)(k-1)}\sum_{a\in A}\delta(A\setminus\{a\}).$ (5)

Proof.

(a) There are maps $\phi_{1}:X\rightarrow\mathbb{R}^{p}$ and $\phi_{2}:X\rightarrow\mathbb{R}^{q}$ and convex bodies $K_{1}\subset\mathbb{R}^{p}$ and $K_{2}\subset\mathbb{R}^{q}$ such that $\delta_{1}(A)=R(\phi_{1}(A),K_{1})$ and $\delta_{2}(A)=R(\phi_{2}(A),K_{2})$ for all $A\subseteq X$ .

Then for all $A\subseteq X$ we have

\lambda\delta_{1}(A)=R(\phi_{1}(A),\lambda^{-1}K_{1})

and by Proposition 4

(\delta_{1}\vee\delta_{2})(A)=R(\phi_{1}(A)\times\phi_{2}(A),K_{1}\times K_{2}).

(b) If there are $\lambda\geq 0$ and $x$ such that $A+x\subseteq\lambda K$ then $\phi(A)+\phi(x)\subseteq\lambda\phi(K)$ so $R(\phi(A),\phi(K))\leq R(A,K)$ . Applying the inverse map gives equality.
(c) There is a map $\phi:X\rightarrow\mathbb{R}^{d}$ and a convex body $K$ such that $R(\phi(A),K)=\delta(A)$ . Applying Proposition 3 gives the result. ∎

We now consider Minkowski-embeddability for a few key examples of symmetric diversities.

Proposition 13.

(a)

The diversity $(X,\delta)$ with $\delta(A)=1$ for all $A\subseteq X$ with $|A|>1$ is Minkowski-embeddable.
(b)

The diversity $(X,\delta)$ with $\delta(A)=|A|-1$ for all non-empty $A\subseteq X$ is Minkowski-embeddable.
(c)

Any diversity $(X,\delta)$ with $X=\{a,b,c\}$ and $\delta(\{a,b\})=\delta(\{a,c\})=\delta(\{b,c\})=1$ is Minkowski-embeddable.

Proof.

(a) Let $n=|X|-1$ . Let $K$ be the simplex with vertex set $V$ given by the standard basis vectors in $\mathbb{R}^{n}$ together with $0$ . Then for non-singleton subset $V^{\prime}\subseteq V$ we have $R(V^{\prime},K)=1$ . Hence any bijection from $X$ to $V$ gives an isometric embedding.
(b) Let $K$ be the same simplex as in (a) and now let $V$ be the vertex set of $-K$ . The proof of Theorem 4.1 in [2] then gives $R(V^{\prime},K)=|V^{\prime}|-1$ for all non-empty subsets of $V^{\prime}\subseteq V$ . The result follows.
(c) Let $x=\delta(\{a,b,c\})$ . As $(X,\delta)$ is a diversity, $1\leq x\leq 2$ . Let $(X,\delta_{1})$ be the diversity on $X$ with $\delta_{1}(A)=1$ for all non-singleton $A\subseteq X$ and let $(X,\delta_{2})$ be the diversity on $X$ with $\delta_{2}(A)=|A|-1$ for all non-empty $A\subseteq X$ . Then $(X,\delta_{1})$ and $(X,\delta_{2})$ are Minkowski-embeddable, and by Proposition 12 (a) so is

(X,\delta)=(X,\delta_{1}\vee(\mbox{$\frac{x}{2}$}\delta_{2})).

∎

We now give an exact characterization for when a finite symmetric diversity is Minkowski-embeddable.

Theorem 14.

Let $(X,\delta)$ be a finite symmetric diversity. Then $(X,\delta)$ is Minkowski-embeddable if and only if

\frac{\delta(A\setminus\{a\})}{\delta(A)}\geq\frac{|A|-2}{|A|-1}

(6)

for all $A\subseteq X$ with $|A|\geq 2$ , $a\in A$ .

Proof.

Suppose that $(X,\delta)$ is Minkowski-embeddable, that $A\subseteq X$ , $|A|\geq 2$ and $a\in A$ .

If $|A|=2$ then (6) holds trivially. If $|A|>2$ then by Proposition 12 (c)

	$\displaystyle\delta(A)$	$\displaystyle\leq\frac{\|A\|-1}{\|A\|(\|A\|-2)}\sum_{x\in A}\delta(A\setminus\{x\})$
		$\displaystyle=\frac{\|A\|-1}{\|A\|(\|A\|-2)}\|A\|\delta(A\setminus\{a\}),$

where the last line follows since $\delta$ is symmetric. Hence (6) holds.

Conversely, suppose that (6) holds for all $A\subseteq X$ such that $|A|\geq 2$ and $a\in A$ . As $(X,\delta)$ is symmetric, $\delta$ is monotonic and there is an increasing function $f:\mathbb{Z}\rightarrow\mathbb{R}_{\geq 0}$ such that $\delta(A)=f(|A|-1)$ for all non-empty $A\subseteq X$ . Note that for each $k=2,\ldots,|X|$ , choosing an $A\subseteq X$ with $|A|=k$ and substituting $A$ into (6) gives

\frac{f(k-2)}{f(k-1)}\geq\frac{k-2}{k-1},

(7)

a fact that we shall use later on in the proof.

Let $X=\{x_{1},x_{2},\ldots,x_{n}\}$ and for each $m\leq n$ define $X_{m}=\{x_{1},x_{2},\ldots,x_{m}\}$ . We will use induction on $m$ to show that for each $m\leq n$ the symmetric diversity $(X,\delta)$ restricted to $X_{m}$ is Minkowski-embeddable. This is clearly the case when $m\leq 2$ .

Suppose that $2<m\leq n$ and that $(X,\delta)$ restricted to $X_{m-1}$ is Minkowski-embeddable. Then there is a map $\phi:X_{m-1}\rightarrow\mathbb{R}^{d}$ for some $d$ and a convex body $K\subseteq\mathbb{R}^{d}$ such that

\delta_{K}(\phi(A))=\delta(A)

for all $A\subseteq X_{m-1}$ . We now define a collection $\delta^{(i)}$ of (semi)diversities on $X_{m}$ , $1\leq i\leq m$ .

First, for each $i=1,2,\ldots,m-1$ define the map $\phi^{(i)}:X_{m}\rightarrow\mathbb{R}^{d}$ by $\phi^{(i)}(x)=\phi(x)$ if $x\in X_{m-1}$ and $\phi^{(i)}(x_{m})=\phi(x_{i})$ . We then define $(X_{m},\delta^{(i)})$ by

\delta^{(i)}(A)=\delta_{K}(\phi^{(i)}(A)).

Since $(\mathbb{R}^{d},\delta_{K})$ is a diversity, $(X_{m},\delta^{(i)})$ satisfies (D1’) and (D2), and so $(X_{m},\delta^{(i)})$ is a Minkowski-embeddable semidiversity. Moreover, the definitions of $\phi$ and $\phi^{(i)}$ give

\delta^{(i)}(A)=\begin{cases}f(|A|-2)&\mbox{ if $x_{i},x_{m}\in A$ }\\ f(|A|-1)&\mbox{ otherwise.}\end{cases}

Second, let $(X_{m},\delta^{(m)})$ be the diversity defined by setting

\delta^{(m)}(A)=\frac{|A|-1}{m-1}f(m-1)

for all non-empty $A\subseteq X_{m}$ . This is Minkowski-embeddable by Proposition 13 (b) and Proposition 12 (a).

We now claim that

\delta(A)=\max\{\delta^{(i)}(A):i=1,\ldots,m\}

(8)

holds for all $A\subseteq X_{m}$ . Proving this claim will complete the proof of the theorem by induction since each (semi)diversity $\delta^{(i)}$ is Minkowski-embeddable, and hence by Proposition 12 (a) $(X_{m},\delta)$ is Minkowski-embeddable.

When $|A|\leq 1$ , (8) holds trivially, as all relevant quantities are zero. Suppose $|A|\geq 2$ . Three cases may hold:

•

$x_{i}\not\in A$ for some $i=1,\ldots,m-1$ ; then $\delta^{(i)}(A)=f(|A|-1)$ .
•

$x_{m}\not\in A$ ; then $\delta^{(i)}(A)=f(|A|-1)$ for all $i=1,\ldots,m-1$ .
•

$A=X_{m}$ ; then $\delta^{(i)}(A)=f(|A|-2)$ for all $i=1,\ldots,m-1$ .

Hence

\max\{\delta^{(i)}(A):i=1,2,\ldots,m-1\}=\begin{cases}f(|A|-1)&\mbox{ if $A\neq X_{m}$;}\\ f(|A|-2)&\mbox{ if $A=X_{m}$.}\end{cases}

We now consider $\delta^{(m)}$ and $A\subseteq X_{m}$ . If $A=X_{m}$ then

\delta^{(m)}(A)=\frac{(|A|-1)}{(m-1)}f(m-1)=f(m-1).

Otherwise suppose $1<|A|<m$ and so

$\displaystyle\delta^{(m)}(A)$	$\displaystyle=\frac{(\|A\|-1)}{(m-1)}f(m-1),$
	$\displaystyle=\frac{(\|A\|-1)}{(m-1)}\left(\prod_{k=\|A\|+1}^{m}\frac{f(k-1)}{f(k-2)}\right)f(\|A\|-1),$
	$\displaystyle\leq\frac{(\|A\|-1)}{(m-1)}\left(\prod_{k=\|A\|+1}^{m}\frac{k-1}{k-2}\right)f(\|A\|-1)$	by (7),
	$\displaystyle=f(\|A\|-1).$

Hence if $A\neq X_{m}$ ,

\max\{\delta^{(i)}(A):i=1,2,\ldots,m\}=\max\{f(|A|-1),\delta^{(m)}(A)\}=f(|A|-1),

while if $A=X_{m}$ then since $f$ is increasing

\max\{\delta^{(i)}(A):i=1,2,\ldots,m\}=\max\{f(|A|-2),\delta^{(m)}(A)\}=f(|A|-1).

We conclude that $\delta(A)=\max\{\delta^{(i)}(A):i=1,\ldots,m\}$ for all $A\subseteq X_{m}$ which completes the proof of (8) and also the theorem. ∎

By considering the diversity on $X=\{a,b,c,d\}$ with

\delta(A)=\begin{cases}2,&|A|=4,\\ 1,&2\leq|A|\leq 3,\\ 0,&\mbox{otherwise,}\end{cases}

and taking $A=\{b,c,d\}$ in Theorem 14 we immediately obtain

Corollary 15.

There exists a diversity a set of four elements that is not Minkowski-embeddable.

We show later (Corollary 18) that every diversity on three elements is Minkowski-embeddable.

5 Parallelotopes and simplices

We have shown that not every diversity is Minkowski-embeddable, and so the question now becomes one of characterizing which diversities are. In this section we characterize when we can embed the diameter and negative-type diversities defined in the introduction in terms of Minkowski diversities having kernels equal to parallelotopes and simplices, respectively.

We first consider diameter diversities.

Theorem 16.

A finite diversity $(X,\delta)$ can be embedded in a Minkowski diversity with kernel equal to some parallelotope if and only if $(X,\delta)$ is a diameter diversity.

Proof.

First note that if there is some such embedding then $(X,\delta)$ is a diameter diversity by Proposition 3.4 of [2].

Conversely, suppose that $X=\{x_{1},x_{2},\ldots,x_{n}\}$ and $(X,\delta)$ is a diameter diversity. Let $\phi:X\rightarrow\mathbb{R}^{n}$ be the standard Fréchet embedding

\phi:X\rightarrow\mathbb{R}^{n}:y\mapsto(d(x_{1},y),d(x_{2},y),\ldots,d(x_{n},y))

of the metric $d$ induced by $\delta$ . Then $d(x,y)=\|\phi(x)-\phi(y)\|_{\infty}$ for all $x,y\in X$ .

Let $K$ be the unit cube in $\mathbb{R}^{n}$ . For all $A\subseteq X$ we have

	$\displaystyle\delta(A)$	$\displaystyle=\max_{a,b\in A}d(a,b)$
		$\displaystyle=\max_{a,b\in A}\\|\phi(a)-\phi(b)\\|_{\infty}$
		$\displaystyle=\max_{i}\max_{a,b\in A}\|\phi(a)_{i}-\phi(b)_{i}\|$
		$\displaystyle=R(\phi(A),K).$

∎

We now consider finite diversities of negative type, the diversity analog of metrics of negative type [14]. Note that the cone of all diversities on a set $X$ of cardinality $n$ has dimension $2^{n}-(n+1)$ , the number of subsets $A\subset X$ with $|A|\geq 2$ , see [35]. The set of diversities of negative type forms a cone of the same dimension, indicating that an appropriately chosen ‘random’ diversity could have non-negative type with non-zero probability.

Theorem 17.

A finite diversity $(X,\delta)$ can be embedded in a Minkowski diversity with kernel equal to some simplex if and only if $(X,\delta)$ has negative type.

Proof.

Let $n=|X|$ . From Theorem 7 of [35], $(X,\delta)$ is negative-type if and only if it can be embedded in $(\mathbb{R}^{d},\delta_{neg})$ for some $d$ and

\delta_{neg}(A)=\sum_{i=1}^{d}\max\{a_{i}:a\in A\}-\min\left\{\sum_{i=1}^{d}a_{i}:a\in A\right\}.

Define the polytope

	$\displaystyle K$	$\displaystyle=-\mathrm{conv}(0,e_{1},e_{2},\ldots,e_{d})$
		$\displaystyle=\{x\leq 0:\sum_{i=1}^{d}x_{i}\geq-1\}.$

Suppose $\lambda=R(A,K)$ , so there is $z$ such that $A\subseteq\lambda K+z$ . Then for all $a\in A$ and all $i$ we have $a_{i}-z_{i}\leq 0$ . Hence

z_{i}\geq\max\{a_{i}:a\in A\}.

Let $a^{*}\in A$ minimize $\sum_{i=1}^{d}a^{*}_{i}$ . Then $a^{*}\in\lambda K+z$ implies $\sum_{i=1}^{d}(a^{*}_{i}-z_{i})\geq-\lambda$ and so

	$\displaystyle\lambda$	$\displaystyle\geq\sum_{i=1}^{d}z_{i}-\sum_{i=1}^{d}a^{*}_{i}$
		$\displaystyle\geq\sum_{i=1}^{d}\max\{a_{i}:a\in A\}-\min_{a\in A}\sum_{i=1}^{d}a_{i}$
		$\displaystyle=\delta_{neg}(A).$

Now suppose $\lambda=\delta_{neg}(A)$ . Let $z_{i}=\max\{a_{i}:a\in A\}$ so that $a_{i}-z_{i}\leq 0$ for all $a\in A$ and all $i=1,\ldots,d$ . Furthermore

	$\displaystyle-\lambda$	$\displaystyle=-\sum_{i=1}^{d}z_{i}+\min\left\{\sum_{i=1}^{d}a_{i}:a\in A\right\}$
		$\displaystyle\leq-\sum_{i=1}^{d}z_{i}+\sum_{i=1}^{d}a_{i}$	for all $a\in A$

so that $\sum_{i=1}^{d}(a_{i}-z_{i})\geq-\lambda$ and $a-z\in\lambda K$ for all $a\in A$ . Hence $R(A,K)\leq\delta_{neg}(A)$ .

We have shown that $(X,\delta)$ is of negative type if and only if it can be embedded into a Minkowski diversity with kernel equal to the particular simplex $K$ . The theorem now follows from Proposition 12(b) and the fact that every simplex in $\mathbb{R}^{d}$ can be transformed into another by a non-degenerate affine map.

∎

The last theorem immediately implies that two further classes are Minkowski-embeddable.

Corollary 18.

If $\delta$ is diversity on three elements or a finite diversity that can be embedded in $L_{1}$ , then $\delta$ is Minkowski-embeddable.

Proof.

All three-element diversities and $L_{1}$ -embeddable diversities have negative type [35]. ∎

6 Open problems

We have characterized diversities and functions defined by the generalized circumradius $R(A,K)$ , and established preliminary results on embedding finite diversities into these spaces. Our results suggest several avenues for further investigation.

First, is there a complete characterization of when a finite diversity is Minkowski-embeddable? Indeed it is not even obvious which finite diversities can be embedded into sublinear diversities in $\mathbb{R}^{d}$ .

A second related question is algorithmic in nature: Are there efficient algorithms for determining whether or not a finite diversity can be embedded in some dimension? Interestingly, we note that for the classical case of a circumradius, even though we do not know a characterization for Minkowski-embeddability, we are able to give an efficient algorithm for deciding embeddability (for bounded dimension):

Proposition 19.

Let $(X,\delta)$ be a finite diversity such that $\delta(A)=\max\{\delta(A^{\prime}):A^{\prime}\subseteq A,|A^{\prime}|\leq d+1\}$ for all $A\subseteq X$ . For fixed $d$ , there is an algorithm which runs in polynomial time in $n=|X|$ to determine if $(X,\delta)$ is Minkowski-embeddable in $\mathbb{R}^{d}$ with kernel equal to the unit ball $\mathfrak{B}$ .

Proof.

We begin with a useful observation. Suppose that there is an (unknown) embedding $\phi:X\rightarrow\mathbb{R}^{d}$ such that $\delta(A)=\delta_{\mathfrak{B}}(\phi(A))$ for all $A\subseteq X$ . Note that since the metric induced by $\delta_{\mathfrak{B}}$ is Euclidean so is the one induced by $\delta$ . Let $\psi:X\rightarrow\mathbb{R}^{d}$ be any map which preserves the metrics induced by $\delta$ and $\delta_{\mathfrak{B}}$ . In addition, let $f$ be the (unknown) isometry from $\psi(X)$ to $\phi(X)$ given by $f(\psi(x))=\phi(x)$ for all $x\in X$ . As $\mathbb{R}^{d}$ is a finite dimensional Hilbert space, $f$ can be extended to an isometry on the whole space $\mathbb{R}^{d}$ (see, e.g., [34], Theorem 11.4). Moreover, for any $A\subseteq X$ we have

	$\displaystyle\delta_{\mathfrak{B}}(\psi(A))$	$\displaystyle=\inf\Big{\{}\sup\{\\|\psi(a)-x\\|_{2}:a\in A\}:x\in\mathbb{R}^{d}\Big{\}}$
		$\displaystyle=\inf\Big{\{}\sup\{\\|f(\psi(a))-f(x)\\|_{2}:a\in A\}:x\in\mathbb{R}^{d}\Big{\}}$
		$\displaystyle=\inf\Big{\{}\sup\{\\|\phi(a)-y\\|_{2}:a\in A\}:y\in\mathbb{R}^{d}\Big{\}}$
		$\displaystyle=\delta_{\mathfrak{B}}(\phi(A))$
		$\displaystyle=\delta(A).$

Hence, if $(X,\delta)$ is Minkowski embeddable into $(\mathbb{R}^{d},\delta_{\mathfrak{B}})$ , then the map $\psi$ gives one embedding.

We now present an algorithm for deciding whether or not $(X,\delta)$ is embeddable in $(\mathbb{R}^{d},\delta_{\mathfrak{B}})$ :

1.

Decide whether or not the metric induced by $\delta$ on $X$ is Euclidean. If not, then $(X,\delta)$ cannot be embedded in $(\mathbb{R}^{d},\delta_{\mathfrak{B}})$ . Else, compute a (metric) embedding $\psi$ of $X$ in $\mathbb{R}^{d}$ which preserves the induced metrics.
2.

If $\delta_{\mathfrak{B}}(\psi(A))=\delta(A)$ for all $A$ with $|A|\leq d+1$ then $(X,\delta)$ can be embedded in $(\mathbb{R}^{d},\delta_{\mathfrak{B}})$ , otherwise $(X,\delta)$ cannot be embedded in $(\mathbb{R}^{d},\delta_{\mathfrak{B}})$ .

The correctness of this algorithm follows by the observation above. To see that it also runs in polynomial time in $n$ (for fixed $d$ ), note that Step 1 can be computed in polynomial time in $n$ by the results in e.g. [14, Section 6.2] or [34, Theorem 2.1], and that for Step 2 the definition of $\delta$ and Proposition 2 imply that to determine whether $\delta_{\mathfrak{B}}(\psi(A))=\delta(A)$ for all $A\subseteq X$ we need only check subsets $A$ with $|A|\leq d+1$ . ∎

Another question is how to extend the embedding results to include distortion. Let $(X_{1},\delta_{1})$ and $(X_{2},\delta_{2})$ be two diversities. We say that a map $\phi:X_{1}\rightarrow X_{2}$ has distortion $c$ if there are $c_{1},c_{2}>0$ such that $c=c_{1}c_{2}$ and

\frac{1}{c_{1}}\delta_{1}(A)\leq\delta_{2}(\phi(A))\leq c_{2}\delta_{1}(A)

for all finite $A\subseteq X$ . Continuing the program of [25], it is shown in [10] that bounds on the distortion of embeddings from diversities into $L_{1}$ -diversities provide approximation algorithms for hypergraph generalizations of sparsest cut. It was shown in [35] that there are finite diversities of metric type which cannot be embedded into $L_{1}$ without at least $\Omega(\sqrt{\log|X|})$ distortion. This bound therefore holds for Minkowski-embeddable diversities. In general, questions concerning distortion seem intricately connected with core sets of the generalized circumradius [2].

Apart from potential algorithmic gains it would be good to explore embeddings with distortion for diversities into Minkowski diversities with low dimension, simply for their use in visualization and modelling of diversity type data.

Acknowledgments

We thank Pei Wu and Malcolm Jones for discussions and ideas which helped initiate this paper. PT is supported by an NSERC (Canada) Discovery Grant. DB, KTH and VM thank the Royal Society for its support. We also thank the reviewers for their helpful comments.

References

[1] Blumenthal, L. M. Theory and Applications of Distance Geometry, 2nd ed., vol. 242. Chelsea Publishing Company, 1970.
[2] Brandenberg, R., and König, S. No dimension-independent core-sets for containment under homothetics. Discrete and Computational Geometry 49 (2013), 3–21.
[3] Brandenberg, R., and König, S. Sharpening geometric inequalities using computable symmetry measures. Mathematika 61 (2015), 559–580.
[4] Brandenberg, R., and Roth, L. Minimal containment under homothetics: a simple cutting plane approach. Computational Optimization and Applications 48, 2 (2011), 325–340.
[5] Bryant, D., Cioica-Licht, P., Clark, L. O., and Young, R. Inner products for convex bodies. Journal of Convex Analysis 28, 4 (2021), 1249–1264.
[6] Bryant, D., Felipe, R., Toledo-Acosta, M., and Tupper, P. F. Lattice diversities. arXiv 2010.11442 (under submission), 2020.
[7] Bryant, D., Nies, A., and Tupper, P. F. A universal separable diversity. Analysis and geometry in metric spaces 5, 1 (2017), 138–151.
[8] Bryant, D., Nies, A., and Tupper, P. F. Fraïssé limits for relational metric structures. Journal of Symbolic Logic 86, 3 (2021), 913–934.
[9] Bryant, D., and Tupper, P. F. Hyperconvexity and tight-span theory for diversities. Advances in Mathematics 231, 6 (2012), 3172–3198.
[10] Bryant, D., and Tupper, P. F. Diversities and the geometry of hypergraphs. Discrete Mathematics and Theoretical Computer Science 16, 2 (2014), 1–20.
[11] Bryant, D., and Tupper, P. F. Constant distortion embeddings of symmetric diversities. Analysis and Geometry in Metric Spaces 4, 1 (2016), 326–335.
[12] Croitoru, A. Set-norm continuity of set multifunctions. ROMAI Journal 6, 1 (2010), 47–56.
[13] Danzer, L., Grünbaum, B., and Klee, V. Helly’s theorem and its relatives. In Convexity, V. Klee, Ed., vol. 7 of Proceedings of Symposia in Pure Mathematics. AMS, Providence, RI, 1963, pp. 101–180.
[14] Deza, M. M., and Laurent, M. Geometry of Cuts and Metrics, vol. 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.
[15] Dokania, P. K. High-Order Inference, Ranking, and Regularization Path for Structured SVM. PhD thesis, Université Paris Saclay (COmUE), 2016.
[16] González Merino, B., Jahn, T., and Richter, C. Uniqueness of circumcenters in generalized Minkowski spaces. Journal of Approximation Theory 237 (2019), 153–159.
[17] Gritzmann, P., and Klee, V. Inner and outer $j$ -radii of convex bodies in finite-dimensional normed spaces. Discrete & Computational Geometry 7 (1992), 255–280.
[18] Gritzmann, P., and Klee, V. Computational complexity of inner and outer $j$ -radii of polytopes in finite-dimensional normed spaces. Mathematical Programming 59 (1993), 163–213.
[19] Gritzmann, P., and Klee, V. On the complexity of some basic problems in computational convexity: I. Containment problems. Discrete Mathematics 136, 1-3 (1994), 129–174.
[20] Hallbäck, A. Metric model theory, Polish groups & diversities. PhD thesis, Université de Paris, 2020.
[21] Jahn, T. Extremal radii, diameter and minimum width in generalized Minkowski spaces. Rocky Mountain Journal of Mathematics 47, 3 (2017), 825–848.
[22] Jahn, T. Successive radii and ball operators in generalized Minkowski spaces. Advances in Geometry 17, 3 (2017), 347–354.
[23] Kirk, W., and Shahzad, N. Diversities. In Fixed Point Theory in Distance Spaces, W. Kirk and N. Shahzad, Eds. Springer International Publishing, Cham, 2014, pp. 153–158.
[24] Komodakis, N., Pawan Kumar, M., and Paragios, N. (Hyper)-graphs inference through convex relaxations and move making algorithms: Contributions and applications in artificial vision. Foundations and Trends in Computer Graphics and Vision 10, 1 (2014), 1–102.
[25] Linial, N., London, E., and Rabinovich, Y. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2 (1995), 215–245.
[26] Pia̧tek, B. On the gluing of hyperconvex metrics and diversities. Annales Universitatis Paedagogicae Cracoviensis. 149, Studia Mathematica 13, 1 (2014), 65–76.
[27] Poelstra, A. On the topological and uniform structure of diversities. Journal of Function Spaces 2013 (2013), Article ID 675057.
[28] Rudin, W., et al. Principles of mathematical analysis, vol. 3. McGraw-hill New York, 1976.
[29] Schneider, R. Convex bodies: the Brunn–Minkowski theory, 2nd ed. Encyclopedia of Mathematics and It Applications. Cambridge University Press, Cambridge, 2014.
[30] Steel, M. Tracing evolutionary links between species. American Mathematical Monthly 121, 9 (2014), 771–792.
[31] Steel, M. Continuous phylogenies and distance-based tree reconstruction. In Phylogeny. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2016, ch. 6, pp. 111–145.
[32] Sylvester, J. J. A question in the geometry of situation. Quarterly Journal of Pure and Applied Mathematics 1 (1857), 79–80.
[33] Toledo Acosta, G. M. Generalizaciones sobre la noción de diversidades. PhD thesis, Centro de Investigación en Matemáticas A.C., 2016.
[34] Wells, J. H., and Williams, L. R. Embeddings and Extensions in Analysis, vol. 84. Springer Science & Business Media, New York, 1975.
[35] Wu, P., Bryant, D., and Tupper, P. F. Negative-type diversities, a multi-dimensional analogue of negative-type metrics. The Journal of Geometric Analysis 31 (2021), 1703–1720.

$\displaystyle\delta^{(m)}(A)$	$\displaystyle=\frac{(\|A\|-1)}{(m-1)}f(m-1),$
	$\displaystyle=\frac{(\|A\|-1)}{(m-1)}\left(\prod_{k=\|A\|+1}^{m}\frac{f(k-1)}{f(k-2)}\right)f(\|A\|-1),$
	$\displaystyle\leq\frac{(\|A\|-1)}{(m-1)}\left(\prod_{k=\|A\|+1}^{m}\frac{k-1}{k-2}\right)f(\|A\|-1)$	by (7),
	$\displaystyle=f(\|A\|-1).$