# Diversities and the Generalized Circumradius

David Bryant  Department of Mathematics and Statistics, University of Otago,
Dunedin, New Zealand. email<EMAIL_ADDRESS>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.

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,

  1. (D1)

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

  2. (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. 1.

The diameter of a set

  2. 2.

The length of a shortest Steiner tree connecting a set

  3. 3.

The mean width of a set

  4. 4.

The length of the shortest traveling salesman tour through a set

  5. 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. 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

  1. (a)

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

  2. (b)

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

  3. (c)

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

  4. (d)

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

  5. (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

  1. (a)

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

  2. (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)$.

  3. (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.$

As

$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)\\}.$

Figure 2:  The sets $A,B,B^{\prime}$ in the proof of Proposition 9 with
(translated) kernels $K$ and $K^{\prime}$.

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.

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.

###### 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)

  1. (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.

  1. (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.

  2. (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))$.

  3. (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.

  1. (a)

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

  2. (b)

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

  3. (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. 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. 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.