# Location problems with cutoff

Raoul Müller111Work supported by DFG RTG 2088. 222raoul.mueller@uni-
goettingen.de 333Institute for Mathematical Stochastics, University of
Göttingen, 37077 Göttingen, Germany. Anita Schöbel444Technische Universität
Kaiserslautern, Faculty for Mathematics, and Fraunhofer Institute for
Industrial Mathematics ITWM, 67663 Kaiserslautern, Germany. Dominic
Schuhmacher33footnotemark: 3

###### Abstract

In this paper we study a generalized version of the Weber problem of finding a
point that minimizes the sum of its distances to a finite number of given
points. In our setting these distances may be _cut off_ at a given value
$C>0$, and we allow for the option of an _empty_ solution at a fixed cost
$C^{\prime}$. We analyze under which circumstances these problems can be
reduced to the simpler Weber problem, and also when we definitely have to
solve the more complex problem with cutoff.

We furthermore present adaptions of the algorithm of [Drezner et al., 1991,
Transportation Science 25(3), 183–187] to our setting, which in certain
situations are able to substantially reduce computation times as demonstrated
in a simulation study. The sensitivity with respect to the cutoff value is
also studied, which allows us to provide an algorithm that efficiently solves
the problem simultaneously for all $C>0$.

##  1 Introduction

For a given finite set $\mathcal{A}\subseteq\mathbb{R}^{k}$, a metric $d$ on
$\mathbb{R}^{k}$ and some $q\geq 1$, we study the location problem

$\min_{z\in\mathbb{R}^{k}}\sum_{a\in\mathcal{A}}\min\\{d(a,z)^{q},C\\},$ (1)

where $C>0$ is a cutoff parameter. Additionally we allow the option _not_ to
choose any location in $\mathbb{R}^{k}$ at a fixed cost per point in
$\mathcal{A}$. Without the cutoff $C$ this problem is known as _Weber_
problem, _one-median_ problem, _minisum_ problem, _Fermat-Torricelli_ problem
or (generalized) _barycenter_ problem. In this paper we call an optimal
solution to the problem a _barycenter_. The barycenter problem is among the
best studied problems in location theory, see [LaporteNickelSaldanha] for
recent surveys of existing results and new developments in the field. Many
results exist for different metrics and for various extensions. The problem
(1) introduces the following two extensions to the classic problem.

The first extension is the cutoff $C$ (as in [drezner1991facility]) which
makes the resulting barycenter more robust against outliers. For $q=1$ and
e.g. $d=\ell_{1}$ this robustness is naturally given, but for other distances,
outliers can have a huge effect on the location of the barycenter. A
barycenter can be thought of as a _typical_ representative of a given set of
points. The robustness helps containing this representative property even if
outliers are present.

In the second extension we additionally allow the barycenter to be _empty_ at
a fixed cost which is constant per point in $\mathcal{A}$. This extends the
representative property of the barycenter. If the given points we want to
represent are so scattered that no single point can represent them, we allow
for _no representation_.

Many application of the setting are possible where the cutoff $C$ and the
possibility of having an empty barycenter come in naturally. An example is a
community which has to decide about building a new waste dump. Anyone can
bring their domestic waste for free (but they have the cost of transportation,
given by the distance to the waste dump) or have it collected for a fixed cost
$C$. If no dump is built, the community has to pay a fixed fee per person to
have their waste collected from the waste dump in a nearby city.

In the paper we investigate the two extensions and compare their solutions to
the solutions of the classical problem. We identify cases in which solutions
to the classical problem are still optimal for the problem with cutoff and
cases in which the empty barycenter is optimal. We also treat the cutoff value
$C$ as part of the problem and investigate the sensitivity of an optimal
solution w.r.t $C$.

Algorithmically, the barycenter problem with cutoff has already been studied,
see [drezner1991facility], [aloise2012improved] and [venkateshan2020note]
resulting in an $\mathcal{O}(n^{2})$-algorithm for $n$ being the number of
existing points in $\mathcal{A}$. We refine this algorithm for the two
extensions and experimentally show good computation times.

The remainder of the paper is organized as follows: In the next section we
formally introduce the barycenter problem and its two extensions referring to
existing literature. In Section 3 we look at some universal properties of the
cutoff that will be helpful, when we investigate the relation between the
barycenter problem _with_ and _without_ cutoff in Section 4. Here, we identify
cases in which an optimal solution to the classic problem is also optimal for
the problem with cutoff. Section 5 looks closer at the problem with _empty_
barycenter. We analyze in which cases the empty barycenter is the best
solution. In Section 6 we analyze the sensitivity of the barycenter and the
objective function value in terms of the cutoff value. Section 7 sketches an
application from statistical data analysis, where the barycenter problem with
cutoff and empty set occurs as a subproblem when we compute a “typical” point
pattern based on a given set of point patterns. In Section 8 we present a
simulation study to compare the runtime of the different algorithms. The paper
ends with some discussions and outlook to further research.

##  2 Extensions of the barycenter location problem: cutoff and empty
barycenter

From now on we will always assume that we are give a finite set of locations
$\mathcal{A}\subseteq\mathbb{R}^{k}$, $|\mathcal{A}|=n\in\mathbb{N}$. The
_diameter of $\mathcal{A}$_

$\operatorname{diam}(\mathcal{A}):=\underset{a_{1},a_{2}\in\mathcal{A}}{\max}d(a_{1},a_{2})$

is the maximum distance between two points of $\mathcal{A}$. For technical
reasons we assume that $\operatorname{diam}(\mathbb{R}^{k})=\infty$. In this
paper we mainly consider _norm-metrics_ , i.e., distances

$d^{q}(x,y)=(d(x,y))^{q}=\|y-x\|^{q},\ x,y\in\mathbb{R}^{k},q\geq 1$

_derived from a norm_ $\|\cdot\|$ (and here in particular the Euclidean norm
$\ell_{2}$ and the Manhattan norm $\ell_{1}$), but many results are also true
for general metrics $d$. When we consider $\ell_{p}$ norms we allow
$p\in[1,\infty]$, so the _maximum norm_ is permitted.

#### (Bar$(\mathcal{A})$): The barycenter problem

The classic location problem is to find a point $x\in\mathbb{R}^{k}$ which
minimizes the sum of distances to the given points in $\mathcal{A}$:

$\mathcal{Z}^{\ast}:=\min_{x\in\mathbb{R}^{k}}f(x,\mathcal{A}):=\sum_{a\in\mathcal{A}}d^{q}(x,a).$
(Bar$(\mathcal{A})$)

We call this problem _barycenter problem_ and denote its set of optimal
solutions by $\mathcal{X}^{*}$. If it is clear to which set $\mathcal{A}$ we
refer to we may write $f(x)$ for its objective function instead of
$f(x,\mathcal{A})$.

$(Bar)$ has already been introduced in the 17th century by Fermat for three
points $a_{1}$,$a_{2}$, and $a_{3}$ and for $n$ weighted facilities by Weber
in 1909, see, e.g., the survey [DKSW01]. Actual research concerns versions
with $p$ facilities [Mladenovich07, Drezetal15, MarinPelegrin20], barriers
[kathrinhabil], obnoxious facility location [DreDreSch18], different types of
facilities to be placed [MSsurvey, Sch20], ordered median location problems
[Nickel-Puerto, PuertoRodri20], location under uncertainty
[CorreiaSaldanha20], and others, see [LaporteNickelSaldanha] and references
therein for a recent overview. Here, we consider the following two extensions
of (Bar).

#### (Bar${}_{C}(\mathcal{A})$): The barycenter problem with cutoff

The first extension we consider is to introduce a cutoff in the distance
function: Given a _cutoff value_ $C>0$, we look at the cutoff distance
function

$d^{q}_{C}(x,y):=\min\\{d^{q}(x,y),C\\},\ x,y\in\mathbb{R}^{k},$ (2)

i.e., the distance is not increased any more once it has reached the value
$C$. The corresponding location problem is given as

$\mathcal{Z}_{C}^{\ast}:=\min_{x\in\mathbb{R}^{k}}f_{C}(x,\mathcal{A}):=\sum_{a\in\mathcal{A}}\min\\{d^{q}(x,a),C\\}.$
(Bar${}_{C}(\mathcal{A})$)

It is called _barycenter problem with cutoff_. We denote its set of optimal
solutions by $\mathcal{X}^{*}_{C}$. Again, if the set $\mathcal{A}$ is known,
we may write $f_{C}(x)$ instead of $f_{C}(x,\mathcal{A})$. The problem is a
special case of the _Weber problem with limited distance_ from
[drezner1991facility]. The latter problem allows different cutoff values
$\lambda_{i}$ for each of the existing facilities while in (BarC) all
$\lambda_{i}=C$. It has also been studied in [aloise2012improved] and
[venkateshan2020note]. Recently, (Bar${}_{C}(\mathcal{A})$) has been
investigated within a statistical application, namely for finding barycenters
for point patterns, see [muller2020metrics] or Section 7. At the end of
Section 3 we present the algorithm of [drezner1991facility] for solving the
Weber problem with limited distances.

Related work includes [fernandes2017polynomial] where the authors consider a
discrete version of a barycenter problem in which they restrict how many
existing points have to be within the cutoff distance. The problem is solved
by a global optimization algorithm based on a decomposition of the plane into
regions for which we know which given points are within the cutoff value $C$.
A reversed approach in which one tries to cover as many points as possible
within a given threshold value $C$ and measures only the distance to the non-
covered points is investigated in [BJKS13].

Note that the cutoff does not change the properties of the distances.
Definiteness, symmetry and triangle inequality are still satisfied.

######  Lemma 1 ([muller2020metrics]).

If $d$ is a metric then $d_{C}$ is also a metric.

#### (Bar${}_{C,\alpha}(\mathcal{A})$): The empty barycenter as an option.

The largest distance to the new facility in (Bar${}_{C}(\mathcal{A})$) is
bounded by the cutoff value $C$. In the second extension we go a step further
and allow to place no facility (represented as $x=\emptyset$). In this case,
each demand point $a\in\mathcal{A}$ has to pay a price of
$C^{\prime}:=\alpha\cdot C$ for some given $\alpha>0$. In order to formulate
this setting as location problem, we extend the metric space by the empty set
$\emptyset$ for which we define a constant “distance” between $x=\emptyset$
and any other point $y\in\mathbb{R}^{k}\cup\emptyset$, namely

$d^{q}_{C,\alpha}(\emptyset,y)=\left\\{\begin{array}[]{ll}\alpha\cdot C&\mbox{
if }y\not=\emptyset\\\ 0&\mbox{ if }y=\emptyset\end{array}\right.$

and leave $d^{q}_{C,\alpha}(x,y)=d^{q}_{C}(x,y)$ for all $x,y\not=\emptyset$.
The corresponding location problem

$\mathcal{Z}_{C,\alpha}^{\ast}:=\min_{x\in\mathbb{R}^{k}\cup\\{\emptyset\\}}f_{C,\alpha}(x,\mathcal{A}):=\sum_{a\in\mathcal{A}}d^{q}_{C,\alpha}(x,a),$
(Bar${}_{C,\alpha}(\mathcal{A})$)

is called _barycenter problem with empty set (and cutoff)_. We denote its set
of optimal solutions by $\mathcal{X}^{*}_{C,\alpha}$ and call
$\xi^{\ast}=\emptyset$ the _empty barycenter_. The problem has recently been
introduced and motivated in [muller2020metrics] but to the best of our
knowledge otherwises not been studied.

Adding the empty barycenter to the metric space with cutoff distance $d_{C}$
does not change the properties of the metric space if $\alpha\geq\frac{1}{2}$.

######  Lemma 2.

$M^{\prime}=(\mathbb{R}^{k}\cup\emptyset,d_{C,\alpha})$ is a metric space if
and only if $\alpha\geq\frac{1}{2}$.

###### Proof.

The definiteness and the symmetry of the metric $d_{C,\alpha}$ directly hold
also for $\emptyset$. The triangle inequality

$d_{C,\alpha}(x,y)+d_{C,\alpha}(y,z)\geq d_{C,\alpha}(x,z)$ (3)

can be shown by checking all possible cases:

  * •

If $x,y,z\in M$, (3) is satisfied since $d_{C}$ is a metric.

  * •

If $x=y=z=\emptyset$, or if exactly two of the three points $x,y,z$ are
$\emptyset$, (3) follows directly from the definition of $d_{C,\alpha}$.

  * •

For only $x=\emptyset$ the triangle inequality holds since
$d_{C,\alpha}(y,z)\geq 0$. The same holds for $z=\emptyset$.

We are left with the case that $y=\emptyset$ and $x,z\in M$. In this case, (3)
transfers to

$\alpha C+\alpha C\geq d_{C,\alpha}(x,z)=d_{C}(x,z).$ (4)

We have to show two directions:

$\Longrightarrow$ Let (4) hold for all $x,z\in\mathbb{R}^{k}$. Choose $x,z$
with $d(x,z)>C$, i.e., $d_{C}(x,z)=C$. Then we receive $2\alpha C\geq C$,
i.e., $\alpha\geq\frac{1}{2}$.

$\Longleftarrow$ Let $\alpha\geq\frac{1}{2}$. Then we have that
$d_{C}(x,z)\leq C\leq 2\alpha C$ and (4) is satisfied.

∎

Note that the proof also shows that for a strictly increasing metric $d$ (such
as $\ell_{1}$ or $\ell_{2}$) without cutoff,
$(\mathbb{R}^{k}\cup\\{\emptyset\\},d_{\infty,\alpha})$ never is a metric
space since (3) is always violated for $y=\emptyset$ and $d(x,z)>2\alpha C$.
This is the reason why we do not treat location problems with empty set, but
without cutoff.

### Relations between (Bar$(\mathcal{A})$), (Bar${}_{C}(\mathcal{A})$), and
(Bar${}_{C,\alpha}(\mathcal{A})$)

We summarize a few observations on the relations between the optimal values of
the three problems.

######  Lemma 3.

We always have

  * (i)

$\mathcal{Z}_{C,\alpha}^{\ast}\leq\mathcal{Z}_{C}^{\ast}\leq\mathcal{Z}^{\ast}$

  * (ii)

$\mathcal{Z}_{C}^{\ast}\leq(n-1)\cdot C$

  * (iii)

$\mathcal{Z}_{C,\alpha}^{\ast}\leq C\cdot\min\\{n-1,n\cdot\alpha\\}$.

###### Proof.

  * (i)

Since $d^{q}_{C}(x,y)\leq d^{q}(x,y)$ we get $f_{C}(x)\leq f(x)$ for all
$x\in\mathbb{R}^{k}$, hence also
$\min_{x\in\mathbb{R}^{k}}f_{C}(x)\leq\min_{x\in\mathbb{R}^{k}}f(x)$ and
$\mathcal{Z}_{C}^{\ast}\leq\mathcal{Z}^{\ast}$ holds.

Furthermore, the empty barycenter increases the set of feasible solutions,
i.e., (Bar${}_{C,\alpha}(\mathcal{A})$) is a relaxation of
(Bar${}_{C}(\mathcal{A})$). We conclude
$\mathcal{Z}_{C,\alpha}^{\ast}\leq\mathcal{Z}_{C}^{\ast}$.

  * (ii)

Let $a\in\mathcal{A}$. This is a feasible barycenter with objective value of
$f_{C}(a)=\sum_{a^{\prime}\in\mathcal{A}}d^{q}_{C}(a,a^{\prime})\leq
0+(n-1)\cdot C$, hence an upper bound on (Bar${}_{C}(\mathcal{A})$).

  * (iii)

The empty barycenter is feasible and has an objective value of
$f_{C,\alpha}=n\cdot\alpha\cdot C$, hence an upper bound on
(Bar${}_{C,\alpha}(\mathcal{A})$). Together with (i) and (ii), the result
follows.

∎

##  3 Exploiting the local structure of BarC

We start with some general properties of the cutoff. To this end we need some
further notation.

######  Definition 4.

Let $x\in\mathbb{R}^{k}$. Then

  * •

${\rm active}_{C}(x):=\\{a\in\mathcal{A}:d^{q}(x,a)\leq C\\}$ denotes the
_active points_ w.r.t $x$ and $C$, and

  * •

${\rm const}_{C}(x):=\mathcal{A}\setminus{\rm active}_{C}(x)$ denotes the
_constant points_ w.r.t $x$ and $C$, i.e., the points whose distances remain
locally constant.

When we know the value of $C$ we just write ${\rm active}(x)$ and ${\rm
const}(x)$.

We can now split the objective function into an active and a constant part,

$\displaystyle f_{C}(x,\mathcal{A})$ $\displaystyle=$ $\displaystyle
f_{C}(x,{\rm active}_{C}(x))+f_{C}(x,{\rm const}_{C}(x))$ (5) $\displaystyle=$
$\displaystyle\sum_{a\in{\rm active}_{C}(x)}d^{q}(x,a)+C\cdot|{\rm
const}_{C}(x)|$ $\displaystyle=$ $\displaystyle f(x,{\rm
active}_{C}(x))+C\cdot|{\rm const}_{C}(x)|.$

This decomposition gives us a first basic result showing that the barycenter
problem with cutoff is equivalent to a problem of type (Bar), but w.r.t a
subset of the existing points.

The following Lemma is an extension of Lemma $2$ of [drezner1991facility], who
proved this result for $d\in\\{\ell_{1},\ell_{2}\\}$, but it is visible that
the proof works more generally. For the sake of completeness we present a
proof for any metric $d$ and any $q\geq 1$.

######  Lemma 5.

Let $\xi^{\ast}\in\mathcal{X}^{*}_{C}$ be an optimal solution to
(Bar${}_{C}(\mathcal{A})$). Then the following hold:

  1. (i)

$\xi^{\ast}$ is an optimal solution to (Bar(${\rm active}(\xi^{\ast})$)).

  2. (ii)

All optimal solutions for (Bar(${\rm active}(\xi^{\ast})$)) are optimal
solutions to (Bar${}_{C}(\mathcal{A})$) i.e., $\mathcal{X}^{*}({\rm
active}(\xi^{\ast}))\subseteq\mathcal{X}^{*}_{C}(\mathcal{A})$.

###### Proof.

  1. ad (i)

Let $\xi^{\ast}\in\mathbb{R}^{k}$ be a minimizer of $f_{C}(x,\mathcal{A})$,
but assume $f(y,{\rm active}(\xi^{\ast}))<f(\xi^{\ast},{\rm
active}(\xi^{\ast}))$ for some $y\in\mathbb{R}^{k}$. Due to (5) we then
receive $f_{C}(y,\mathcal{A})<f_{C}(\xi^{\ast},\mathcal{A})$, a contradiction
to the optimality of $\xi^{\ast}$.

  2. ad (ii)

For the second statement, take $\eta^{\ast}\in\mathcal{X}^{*}({\rm
active}(\xi^{\ast}))$. We consider ${\rm active}(\xi^{\ast})$ and ${\rm
const}(\xi^{\ast})=\mathcal{A}\setminus{\rm active}(\xi^{\ast})$ separately:

$\displaystyle f_{C}(\xi^{\ast},{\rm active}(\xi^{\ast}))$ $\displaystyle=$
$\displaystyle f(\xi^{\ast},{\rm active}(\xi^{\ast}))=f(\eta^{\ast},{\rm
active}(\xi^{\ast}))\ \geq\ f_{C}(\eta^{\ast},{\rm active}(\xi^{\ast}))$
$\displaystyle f_{C}(\xi^{\ast},{\rm const}(\xi^{\ast}))$ $\displaystyle=$
$\displaystyle\sum_{a\in{\rm const}(\xi^{\ast})}C\ \geq\ \sum_{a\in{\rm
const}(\xi^{\ast})}\min\\{d^{q}(\eta^{\ast},a),C\\}\ =\ f_{C}(\eta^{\ast},{\rm
const}(\xi^{\ast}))$

and together we receive that $f_{C}(\eta^{\ast},\mathcal{A})\leq
f_{C}(\xi^{\ast},\mathcal{A})$, hence $\eta^{\ast}$ is also optimal.

∎

This result is one of the main ideas needed for Algorithm 1 and its improved
versions which are described next. We state the approach of
[drezner1991facility] for our special case of cut off distances. Note that the
versions of [aloise2012improved] and [venkateshan2020note] are not relevant
for this setting.

Input : Set $\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}$, cutoff $C>0$

Output : A barycenter $\xi^{\ast}$ of $\eqref{cutoff}$, objective function
value $\mathcal{Z}_{C}^{\ast}$

1 Set $\xi^{\ast}\leftarrow a_{1}$, $\mathcal{Z}_{C}^{\ast}\leftarrow\infty$;

2 for  _$i\leftarrow 1$ to $(n-1)$_ do

3 Inner Loop;

4

5 end for

6return _$\xi^{\ast},\mathcal{Z}_{C}^{\ast}$_

Inner Loop:

7for  _$j\leftarrow(i+1)$ to $n$_ do

8 if  _$d^{q}(a_{i},a_{j})\leq 2^{q}\cdot C$_ then

9 Compute the centers $c_{1},c_{2}$ of the balls with radius $C$ that fulfill
$d^{q}(c_{1},a_{i})=d^{q}(c_{1},a_{j})=d^{q}(c_{2},a_{i})=d^{q}(c_{2},a_{j})=C$;

10 for  _$k\leftarrow 1$ to $2$_ do

11 Set $S:=\\{a\in\mathcal{A}\ |\ d^{q}(c_{k},a)\leq C\\}$;

12 Compute for the four sets
$S,S\setminus\\{a_{i}\\},S\setminus\\{a_{j}\\},S\setminus\\{a_{i},a_{j}\\}$
the barycenters $\xi_{1},\ldots\xi_{4}$ and the corresponding objective
function values $d_{1},\ldots d_{4}$;

13 $l\leftarrow\underset{l\in\\{1,\ldots,4\\}}{\min}d_{l}$;

14 if  _$d_{l} <\mathcal{Z}_{C}^{\ast}$_ then

15 $\mathcal{Z}_{C}^{\ast}\leftarrow d_{l}$, $\xi^{\ast}\leftarrow\xi_{l}$;

16

17 end if

18

19 end for

20

21 end if

22

23 end for

Algorithm 1 Algorithm for (Bar${}_{C}(\mathcal{A})$), based on
[drezner1991facility].

The following observations are true in the plane. We know from Lemma 5 that
any optimal solution to (Bar${}_{C}(\mathcal{A})$) is a solution to (Bar($A$))
for a subset $A\subseteq\mathcal{A}$. Algorithm 1 uses brute force to
calculate the optimal solutions for these subsets. But instead of enumerating
all theoretically possible $2^{n}-1$ subsets, [drezner1991facility] use the
following geometric observation to cut down the number of subsets to look at:
Say we have an optimal solution $\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$. Set
$A:={\rm active}(\xi^{\ast})$. $A$ is contained in a ($2$-dimensional) ball
around $\xi^{\ast}$ with radius $C$. This ball can be ”moved” so that two
points, $a_{1},a_{2}$ of $\mathcal{A}$ lie on the circumference of the ball
and all points of $A$ are still inside. We hence can restrict our search to
all balls with radius $C$ that are defined by two points of $\mathcal{A}$ on
its circumference. [drezner1991facility] proved that there are at most
$\mathcal{O}(n^{2})$ of these balls, so we only need to solve (Bar($A$)) for
$\mathcal{O}(n^{2})$ subsets. The arguments of the proof hold for all norm
metrics $d$ and all $q\geq 1$, although [drezner1991facility] did not state
these cases explicitly.

######  Theorem 6 ([drezner1991facility]).

Let $\mathcal{A}\subseteq\mathbb{R}^{2}$, let $d$ be a norm-metric and say we
can solve (Bar$(\mathcal{A})$) in $h(n)$ time. Then Algorithm 1 solves the
problem (Bar${}_{C}(\mathcal{A})$) in $\mathcal{O}(n^{2}\cdot h(n))$ time.

###### Proof.

The result was proven in [drezner1991facility] for
$d\in\\{\ell_{1},\ell_{2}\\}$. The proof is based on two arguments. First the
solution of (Bar${}_{C}(\mathcal{A})$) is a solution to (Bar(A)) for some
$A\subseteq\mathcal{A}$. And second the number of these subsets $A$ we need to
check for the optimal solution is of order $n^{2}$. Lemma 5 states the first
argument for any metric $d$ and any $q\geq 1$. And the second argument follows
directly from the proof of Theorem 1 in [drezner1991facility]. The argument in
the proof works for any ball defined by a norm-metric $d$. A ball that is
defined by $d^{q}$ only differs in its radius from a ball that is defined by
$d$. So the number of candidate subsets $A$ is of order $n^{2}$ for any norm-
metric $d$ and any $q\geq 1$. ∎

######  Remark.

Algorithm 1 is presented only for finite subsets $\mathcal{A}$ of
$\mathbb{R}^{2}$. The method of cutting down the number of $2^{n}-1$
theoretically possible subsets of $\mathcal{A}$ to a polynomial number of
subsets also works in $\mathbb{R}^{k}$ for $k\geq 3$. The $k$-dimensional ball
with radius $C$ is uniquely defined by $k$ points that define a $k-1$
dimensional hyperplane. For $k=2$ we need two points that are not identical,
for $k=3$ we need three points that are not collinear. With the same arguments
as for the the $2$-dimensional case, the number of candidate sets is bound by
$\mathcal{O}(\binom{n}{k})$ = $\mathcal{O}(n^{k})$. Therefore Algorithm 1 can
be solved in $k$ dimensions in $\mathcal{O}(n^{k}\cdot h(n))$ time.

We additionally suggest the following improvement that is obtained by
replacing lines $1$-$5$ by Algorithm 2: Instead of investigating all
$a_{i},a_{j}$ with $d(a_{i},a_{j})\leq 2^{q}C$ we sort out points $a_{i}$ for
which we can be sure that they will not lead to a solution that improves our
current best objective function value. The sorting out is based on the
following lemmas.

######  Lemma 7.

Let $a\in\mathcal{A}$ and $A^{\prime}:=\\{a^{\prime}\in\mathcal{A}\ |\
d^{q}(a,a^{\prime})>2^{q}C\\}$. Let $x\in\mathbb{R}^{k}$ s.t. $d^{q}(x,a)\leq
C$. Then

  * (i)

$A^{\prime}\subseteq{\rm const}(x)$,

  * (ii)

$f_{C}(x)\geq C\cdot|A^{\prime}|$.

###### Proof.

  * ad (i)

Take $a^{\prime}\in A^{\prime}$. We know by definition of $A^{\prime}$ that

$d^{q}(a,a^{\prime})>2^{q}C\Rightarrow d(a,a^{\prime})>2\sqrt[q]{C}.$

We also know that

$d^{q}(a,x)\leq C\Rightarrow d(a,x)\leq\sqrt[q]{C}.$

With the triangle inequality we get that

$\underbrace{d(a,a^{\prime})}_{>2\sqrt[q]{C}}-\underbrace{d(a,x)}_{\leq\sqrt[q]{C}}\leq
d(x,a^{\prime}).$

The left side of the inequality is $>\sqrt[q]{C}$. Hence
$\sqrt[q]{C}<d(x,a^{\prime})\Rightarrow C<d^{q}(x,a^{\prime})\Rightarrow
a^{\prime}\in{\rm const}(x)$.

  * ad (ii)

Now we know from (i) that $A^{\prime}\subseteq{\rm const}(x)$. Therefore
$f_{C}(x)\geq C\cdot|{\rm const}(x)|\geq C\cdot|A^{\prime}|$.

∎

######  Lemma 8.

Let $a\in\mathcal{A}$, let $z=f_{C}(x)$ for some $x\in\mathbb{R}^{k}$. Let
$A^{\prime}:=\\{a^{\prime}\in\mathcal{A}\ |\ d^{q}(a,a^{\prime})>2^{q}C\\}$
like in Lemma 7. If $C\cdot|A^{\prime}|>z$ then no set $S\ni a$ constructed in
Algorithm 1 will lead to an optimal solution
$\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$.

###### Proof.

Let $\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$ be an optimal solution to
(Bar${}_{C}(\mathcal{A})$). We know from Lemma 5 that any optimal
$\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$ is a solution of (Bar(${\rm
active}(\xi^{\ast})$)). Say we have constructed a set $S$ containing
$a\in\mathcal{A}$ in line $10$ of Algorithm 1. Suppose there is a
$\xi\in\mathcal{X}^{\ast}_{C}$, such that ${\rm active}(\xi)=S$. We know then
that $f_{C}(\xi)\geq C\cdot|\mathcal{A}\setminus S|$. With Lemma 7(i) and the
construction of the set $S$ we know that $\mathcal{A}\setminus S\supseteq
A^{\prime}$. Therefore $f_{C}(\xi)\geq C\cdot|\mathcal{A}\setminus S|\geq
C\cdot|A^{\prime}|>z\geq\mathcal{Z}^{\ast}_{C}$. Therefore no set $S$ that we
construct in Algorithm 1 that contains the point $a$, nor any of its subsets
are the active set of an optimal solution. ∎

Input : Set $\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}$, cutoff $C>0$

Output : A barycenter $\xi^{\ast}$ of $\eqref{cutoff}$, objective function
value $\mathcal{Z}_{C}^{\ast}$

1 Set $\xi^{\ast}\leftarrow a_{1}$, $\mathcal{Z}_{C}^{\ast}\leftarrow\infty$,
$\mathcal{B}\leftarrow\mathcal{A}$;

2 for  _$i\leftarrow 1$ to $(n-1)$_ do

3 $continue$ $\leftarrow$ $true$;

4 $m\leftarrow|\\{a\in\mathcal{B}\ |\ d^{q}(a_{i},a)\leq 2^{q}C\\}|$;

5 if  _$(n-m)\cdot C\geq\mathcal{Z}_{C}^{\ast}$_ then

6 $\mathcal{B}\leftarrow\mathcal{B}\setminus\\{a_{i}\\}$;

7 $continue$ $\leftarrow$ $false$;

8

9 end if

10 if  _continue_ then

11 Inner Loop;

12

13 end if

14

15 end for

return _$\xi^{\ast},\mathcal{Z}_{C}^{\ast}$_

Algorithm 2 Improvement of Algorithm 1

######  Theorem 9.

Let $\mathcal{A}\subseteq\mathbb{R}^{2}$, let $d$ be a norm-metric and say we
can solve (Bar$(\mathcal{A})$) in $h(n)$ time. Then Algorithm 2 solves the
problem (Bar${}_{C}(\mathcal{A})$) in $\mathcal{O}(n^{2}\cdot h(n))$ time.

###### Proof.

We have to prove two things: first the runtime and second the correctness.
First: The calculation of $m$ takes $\mathcal{O}(n)$ time and hence does not
increase the runtime of the algorithm.
Second: For the correctness we have to prove that although we skip the _Inner
Loop_ for some $a_{i}$ we still compute the optimal solution. Lemma 8 implies
that we can skip any point $a_{i}$ if for
$A^{\prime}:=\\{a^{\prime}\in\mathcal{A}\ |\
d^{q}(a_{i},a^{\prime})>2^{q}C\\}$ the value $|A^{\prime}|\cdot C=(n-m)\cdot
C$ is larger than the current best objective function value. In addition the
proof of Lemma 8 yields that $a_{i}\not\in{\rm active}(\xi^{\ast})$ for
$\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$. It is therefore justified to
permanently remove $a_{i}$ from the candidate set of potentially active points
in line $4$ of Algorithm 2. ∎

Later in Section 5, where we solve (Bar${}_{C,\alpha}(\mathcal{A})$), we can
further reduce the computation time with the knowledge that also any point
$a_{i}$ for which $m\leq(1-\alpha)\cdot n$ can also be disregarded, compare
Lemma 19.

#### Other consequences of Lemma 5

Apart from its algorithmic implication, Lemma 5 has several other consequences
since it transfers properties that depend on the local structure from
(Bar$(\mathcal{A})$) to (Bar${}_{C}(\mathcal{A})$). This holds for properties
which are only based on the metric and on the existing facilities. Such
properties then also hold for subsets of the existing facilities, and in
particular for ${\rm active}(\xi^{*})$ where $\xi^{*}$ is an optimal solution
of (Bar${}_{C}(\mathcal{A})$). A first example of such a condition which will
be used later in Theorem 17 is the property (conv) for (Bar$(\mathcal{A})$)
that there always exists an optimal solution $\xi^{*}$ to the barycenter
problem which is contained in the convex hull ${\rm conv}(\mathcal{A})$ of the
existing facilties.

$\text{ For any subset}A\subseteq\mathcal{A}:\mathcal{X}^{*}(A)\cap{\rm
conv}(A)\neq\emptyset$ (conv)

If (conv) holds for (Bar$(\mathcal{A})$) then it also holds for
(Bar${}_{C}(\mathcal{A})$).

######  Lemma 10.

If (conv) then $\mathcal{X}_{C}^{\ast}(\mathcal{A})\cap{\rm
conv}(\mathcal{A})\neq\emptyset$.

###### Proof.

Let $\xi^{\ast}\in\mathcal{X}^{*}_{C}(\mathcal{A})$. From Lemma 5 we know that
$\xi^{\ast}$ is optimal for Bar$({\rm active}(\xi^{\ast}))$. There exists
$\eta^{\ast}\in\mathcal{X}^{*}({\rm active}(\xi^{\ast}))$ with
$\eta^{\ast}\in{\rm conv}({\rm active}(\xi^{\ast}))\subseteq{\rm
conv}(\mathcal{A})$. From the second part of Lemma 5 we know that
$\eta^{\ast}\in\mathcal{X}^{*}_{C}(\mathcal{A})$. Together, the result
follows. ∎

Condition (conv) is satisfied for many location problems. We list cases in
which it holds below.

  * •

In $\mathbb{R}^{2}$ (and in $\mathbb{R}^{1}$) (conv) holds for all distances
$d$ dervied from norms [plastria1984localization].

  * •

For $k>2$, (conv) only holds in general if $d$ is a norm which is linearly
equivalent to the $\ell_{2}$-norm [plastria1984localization].

  * •

(conv) holds for $d=\ell_{2}^{2}$, since the (unique) optimal solution of
(Bar$(\mathcal{A})$) is in this case the coordinate-wise mean of the points in
$\mathcal{A}$ which is always contained in ${\rm conv}(\mathcal{A})$.

There are many other examples of conditions which can be transferred form
(Bar$(\mathcal{A})$) to (Bar${}_{C}(\mathcal{A})$). Among them are:

  * •

There exists a finite candidate set for (Bar${}_{C}(\mathcal{A})$) if $d$ is
derived from a polyhedral norm. This candidate set can be found by using the
intersection points of the fundamental directions.

  * •

For problems (Bar${}_{C}(\mathcal{A})$) with restricted set $R$ all optimal
solutions are either optimal solutions for the unrestricted problem or are
contained in the boundary of $R$.

Above we stated the property (conv), which will enable us to make a connection
between (Bar$(\mathcal{A})$) and (Bar${}_{C}(\mathcal{A})$) in Theorem 17. We
now state a weaker assumption that also allows for a connection between
(Bar$(\mathcal{A})$) and (Bar${}_{C}(\mathcal{A})$).

$\displaystyle\text{There exists a ball }B=B(x,r)\text{ such that:}$
$\displaystyle\text{for all }A\subseteq\mathcal{A}:\mathcal{X}^{\ast}(A)\cap
B\neq\emptyset$ (B)

######  Lemma 11.

Condition (3) implies that $\mathcal{A}\subseteq B$.

###### Proof.

For any point $a\in\mathcal{A}$ the singleton $\\{a\\}$ is a subset of
$\mathcal{A}$. The optimal solution $\xi^{\ast}$ of (Bar$(\\{a\\})$) is
$\xi^{\ast}=a$. Therefore $B$ must contain all points $a\in\mathcal{A}$. ∎

The set $\mathcal{A}$ is finite. That means there are only finitely many
subsets $A\subseteq\mathcal{A}$ and a ball $B$ that fulfills (3) always
exists. We consider the smallest one.

######  Definition 12.

We define a _ball_ with center $x\in\mathbb{R}^{k}$ and radius $r>0$ by
$B:=B(x,r):=\\{y\in\mathbb{R}^{k}\;|\;d(x,y)\leq r\\}$. We denote by
$B_{0}=B(x_{0},r_{0})$ a _smallest ball_ (in terms of radius) that fulfills
(3).

We can now make a connection between the optimal objective function values
$\mathcal{Z}^{\ast}$ and $\mathcal{Z}^{\ast}_{C}$.

######  Theorem 13.

If $2r_{0}\leq\sqrt[q]{C}$, then $\mathcal{Z}^{\ast}=\mathcal{Z}_{C}^{\ast}$

###### Proof.

Take an optimal solution $\xi^{\ast}$ of (Bar${}_{C}(\mathcal{A})$) inside
$B_{0}$ and an optimal solution $\eta^{\ast}$ of (Bar$(\mathcal{A})$) inside
$B_{0}$. Both solutions must exist due to (3). We prove that
$\mathcal{Z}^{\ast}=f(\eta^{\ast})=f_{C}(\xi^{\ast})=\mathcal{Z}^{\ast}_{C}$.

We know that $\xi^{\ast}\in B_{0}$. That means for every $a\in\mathcal{A}$
that $d(\xi^{\ast},a)\leq d(\xi^{\ast},x_{0})+d(x_{0},a)\leq 2r_{0}$. Then
$d^{q}(\xi^{\ast},a)\leq(2r_{0})^{q}\leq C$ and hence
$f_{C}(\xi^{\ast})=f(\xi^{\ast})$. Analogously we get that
$f(\eta^{\ast})=f_{C}(\eta^{\ast})$. From the optimality of both $\xi^{\ast}$
and $\eta^{\ast}$ it follows that $f_{C}(\xi^{\ast})\leq f_{C}(\eta^{\ast})$
and $f(\eta^{\ast})\leq f(\xi^{\ast})$ and therefore
$f(\xi^{\ast})=f_{C}(\xi^{\ast})\leq f_{C}(\eta^{\ast})=f(\eta^{\ast})\leq
f(\xi^{\ast})$, i.e. $f(\xi^{\ast})=f(\eta^{\ast})$. ∎

We will see in the next section in Lemma 14 that
$\mathcal{Z}^{\ast}=\mathcal{Z}_{C}^{\ast}$ also implies that
$\mathcal{X}^{\ast}\subseteq\mathcal{X}^{\ast}_{C}$.

##  4 Comparing BarC and Bar

In this section we have a closer look at the barycenter problem with cutoff in
comparison to the barycenter problem without cutoff. In general, problem
(Bar$(\mathcal{A})$) has an easier structure than problem
(Bar${}_{C}(\mathcal{A})$). While (Bar$(\mathcal{A})$) is a convex problem for
every norm-metric $d$, the cutoff destroys convexity and can, e.g., lead to
non-connected optimal solution sets. In the following we identify conditions
under which solving (Bar$(\mathcal{A})$) gives us the objective function value
of (Bar${}_{C}(\mathcal{A})$) or even an optimal solution of the latter.

  * (a)

$(Bar)$ has the same objective function value as $(Bar_{C})$, i.e.
$\mathcal{Z}^{*}=\mathcal{Z}^{\ast}_{C}$.

  * (b)

Any solution to $(Bar)$ is a solution to $(Bar_{C})$, i.e.,
$\mathcal{X}^{\ast}\subseteq\mathcal{X}^{\ast}_{C}$.

If the second condition holds then it is sufficient to solve $(Bar)$. We first
show that condition (b) already follows from (a) (but not vice versa), so
either condition is useful.

######  Lemma 14.

If condition $(a)$ holds then $(b)$ holds as well.

###### Proof.

Let $\xi^{\ast}\in\mathcal{X}^{\ast}$ be an optimal solution to
(Bar$(\mathcal{A})$) and $\eta^{\ast}\in\mathcal{X}^{\ast}_{C}$ an optimal
solution to (Bar${}_{C}(\mathcal{A})$). From condition (a) we know that
$f(\xi^{\ast})=f_{C}(\eta^{\ast})$. In order to show that
$\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$, we compute

$f_{C}(\xi^{\ast})\leq f(\xi^{\ast})=f_{C}(\eta^{\ast})\leq
f_{C}(\xi^{\ast}).$

Consequently, $f_{C}(\xi^{\ast})=f_{C}(\eta^{\ast})$ and hence
$\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$. ∎

With this result we know, that as soon as condition $(a)$ holds, we can solve
the problem $(Bar)$ and automatically get a solution to $(Bar_{C})$.

The implication $(b)\Rightarrow(a)$ is not true in general, as a simple one-
dimensional example shows:

######  Example 1 (Counterexample to (b) $\Rightarrow$ (a)).

Let 4 points in $\mathbb{R}$ be given, $a_{1}=a_{2}=0$, $a_{3}=C+\varepsilon$
and $a_{4}=-C-\varepsilon$ and let $q=1$. The solution to both problems,
(Bar$(\mathcal{A})$) and (Bar${}_{C}(\mathcal{A})$) is
$\mathcal{X}^{\ast}=\mathcal{X}^{\ast}_{C}=\\{0\\}$, but
$\mathcal{Z}^{\ast}=2(C+\varepsilon)>2C=\mathcal{Z}^{\ast}_{C}$.

We now show that for a set $\mathcal{A}$ with a large diameter, condition
$(a)$ is not met. To this end, we use that for two points, a barycenter is
given by their arithmetic mean.

######  Lemma 15.

For two points $a,b\in\mathbb{R}^{k}$, for any $\ell_{p}$-norm and for all
$q\geq 1$, a minimizer of $\|a-x\|^{q}+\|b-x\|^{q}$ is $x=\frac{a+b}{2}$.

###### Proof.

For $\ell_{p}$-norms this can be treated as a one-dimensional problem, since
the optimal solutions are on the line between $a$ and $b$. W.l.o.g say
$a=0,b=1$. Every other case follows by scaling. The resulting objective
function is $f(x)=x^{q}+(1-x)^{q}$ whose minimium is attained at
$\bar{x}=\frac{1}{2}$. ∎

The next theorem identifies cases in which condition (a) does not hold; i.e.,
cases in which the objective function value of (Bar${}_{C}(\mathcal{A})$) is
strictly smaller than that of (Bar$(\mathcal{A})$).

######  Theorem 16.

(Bar${}_{C}(\mathcal{A})$) has a strictly smaller objective function value
than (Bar$(\mathcal{A})$) in the following two cases:

  * (i)

$\operatorname{diam}(\mathcal{A})>2C$, $q=1$ and $d$ is a metric,

  * (ii)

$\operatorname{diam}(\mathcal{A})>2\sqrt[q]{C}$, $q>1$ and $d$ is derived from
an $\ell_{p}$-norm.

###### Proof.

Since $\mathcal{A}$ is finite there exist two points $a,b\in\mathcal{A}$ such
that $d(a,b)=\operatorname{diam}(\mathcal{A})>2\sqrt[q]{C}$.

  * ad (i):

for any point $x\in\mathbb{R}^{k}$ the triangle inequality directly gives
$d(x,a)+d(x,b)\geq d(a,b)>2C$.

  * ad (ii):

we use Lemma 15, namely that a minimizer of $\|a-x\|^{q}+\|b-x\|^{q}$ is given
by $\bar{x}=\frac{a+b}{2}$. We receive that for any point
$x\in\mathbb{R}^{k}$:

$\displaystyle d^{q}(a,x)+d^{q}(x,b)$ $\displaystyle=$
$\displaystyle\|a-x\|^{q}+\|x-b\|^{q}\geq\|a-\bar{x}\|^{q}+\|\bar{x}-b\|^{q}$
$\displaystyle=$ $\displaystyle 2^{-(q-1)}\|a-b\|^{q}>2^{-(q-1)}\cdot
2^{q}C=2C.$

In both cases, at least one of the distances $d^{q}(a,x)$ or $d^{q}(x,b)$ is
larger than the cutoff $C$ for any $x\in\mathbb{R}^{k}$. This holds especially
for a barycenter $\xi^{\ast}\in\mathcal{X}^{\ast}$. Therefore

$\displaystyle
f(\xi^{\ast})=\sum_{a\in\mathcal{A}}d^{q}(\xi^{\ast},a)>\sum_{a\in\mathcal{A}}\min\\{d^{q}(\xi^{\ast},a),C\\}=f_{C}(\xi^{\ast}).$

Let $\eta^{\ast}\in\mathcal{X}^{\ast}_{C}$. We know that
$f_{C}(\xi^{\ast})\geq f_{C}(\eta^{\ast})$. Hence,

$\mathcal{Z}^{*}=f(\xi^{\ast})>f_{C}(\xi^{\ast})\geq
f_{C}(\eta^{\ast})=\mathcal{Z}^{*}_{C}.$

∎

The next theorem identifies a setting in which condition (a) and hence also
condition (b) hold, i.e., in which (Bar$(\mathcal{A})$) can be used to obtain
an optimal solution to (Bar${}_{C}(\mathcal{A})$).

######  Theorem 17.

Consider a location problem (Bar$(\mathcal{A})$) which satisfies property
(conv). If $\operatorname{diam}(\mathcal{A})\leq\sqrt[q]{C}$, then
$\mathcal{Z}^{\ast}=\mathcal{Z}^{\ast}_{C}$ and
$\mathcal{X}^{\ast}\subseteq\mathcal{X}^{\ast}_{C}$.

###### Proof.

Let $\xi^{\ast}\in\mathcal{X}^{\ast}$ be an optimal solution to
(Bar$(\mathcal{A})$) and $\eta^{\ast}\in\mathcal{X}^{\ast}_{C}$ be an optimal
solution to (Bar${}_{C}(\mathcal{A})$). By (conv) and Corollary 10 we may
choose both, $\xi^{\ast}$ and $\eta^{\ast}\in{\rm conv}(\mathcal{A})$.

For any point $x\in{\rm conv}(\mathcal{A})$ and for all $a\in\mathcal{A}$ we
have that $d(x,a)\leq\operatorname{diam}(\mathcal{A})\leq\sqrt[q]{C}$,
therefore $d^{q}(x,a)\leq C$ and thus $f(x)=f_{C}(x)$. In particular, we
receive

$\displaystyle f(\xi^{\ast})$ $\displaystyle=$ $\displaystyle
f_{C}(\xi^{\ast})$ $\displaystyle f_{C}(\eta^{\ast})$ $\displaystyle=$
$\displaystyle f(\eta^{\ast}).$

Hence we obtain

$f_{C}(\xi^{\ast})=f(\xi^{\ast})\leq f(\eta^{\ast})=f_{C}(\eta^{\ast})\leq
f_{C}(\xi^{\ast}),$

i.e., $\mathcal{Z}^{*}=f(\xi^{\ast})=f_{C}(\eta^{\ast})=\mathcal{Z}^{*}_{C}$.
By Lemma 14, we also get $\mathcal{X}^{\ast}\subseteq\mathcal{X}^{\ast}_{C}$.
∎

We hence know that $\mathcal{Z}^{*}=\mathcal{Z}^{*}_{C}$ if the diameter of
the set $\mathcal{A}$ is smaller or equal to $\sqrt[q]{C}$ and that
$\mathcal{Z}^{*}>\mathcal{Z}^{*}_{C}$ if the diameter is greater than
$2\sqrt[q]{C}$. The following examples demonstrate that for the remaining
cases, $\sqrt[q]{C}<\operatorname{diam}(\mathcal{A})\leq 2\sqrt[q]{C}$
everything may happen.

######  Example 2.

[Example where (a) holds for $q=1$ and $C<\operatorname{diam}(\mathcal{A})\leq
2C$] Let $n+2$ points in $\mathbb{R}$ be given, $n\geq 2$. Say
$a_{1}=\ldots=a_{n}=0,a_{n+1}=C-\varepsilon,a_{n+2}=-(C-\varepsilon)$. The
diameter of this set is
$\operatorname{diam}(\mathcal{A})=d(a_{n+1},a_{n+2})=2C-2\varepsilon$. Now
$\mathcal{X}^{\ast}=\mathcal{X}^{\ast}_{C}=\\{0\\}$ and
$\mathcal{Z}^{\ast}=\mathcal{Z}^{\ast}_{C}$.

In this case the solution of $(Bar)$ is also a solution of $(Bar_{C})$. But
there are simple examples, where
$\mathcal{X}^{\ast}\not\subseteq\mathcal{X}^{\ast}_{C}$.

######  Example 3.

[Example where (b) does not hold for $q=1$, $d=\ell_{1}$ and
$C<\operatorname{diam}(\mathcal{A})\leq 2C$]

$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$\eta$

Let $5$ points $a_{1}$ to $a_{5}$ in $\mathbb{R}^{2}$ be given with
coordinates
$a_{1}=(-\frac{\varepsilon}{2}/\frac{\varepsilon}{2}),a_{2}=(-\frac{\varepsilon}{2}/-\frac{\varepsilon}{2}),a_{3}=(0/0),a_{4}=(C-\frac{\varepsilon}{4}/\frac{\varepsilon}{4}),a_{5}=(C-\frac{\varepsilon}{4}/-\frac{\varepsilon}{4})$
for some $\varepsilon>0$. The placement is pictured above. We get the
following distances: $d(a_{3},a_{4})=d(a_{3},a_{5})=C$,
$d(a_{1},a_{3})=d(a_{2},a_{3})=\varepsilon$. The diameter of this set is
$d(a_{1},a_{5})=d(a_{2},a_{4})=d(a_{1},a_{3})+d(a_{3},a_{5})=C+\varepsilon$.
The optimal solution of (Bar$(\mathcal{A})$) is $a_{3}$ with
$\mathcal{Z}^{\ast}=2C+2\varepsilon=f_{C}(a_{3})$. For
$\eta=(-\frac{\varepsilon}{2}/0)$ we get
$f_{C}(\eta)=\frac{3\varepsilon}{2}+2C<f_{C}(a_{3})$. Thus
$a_{3}\in\mathcal{X}^{\ast}$ but $a_{3}\not\in\mathcal{X}_{C}^{\ast}$.

######  Example 4.

[Example where (b) does not hold for $q=1$, $d=\ell_{2}$ and
$C<\operatorname{diam}(\mathcal{A})\leq 2C$]

$a_{1}$$a_{2}$$\xi$$a_{3}$$\eta$

Let $3$ points $a_{1}$ to $a_{3}$ in $\mathbb{R}^{2}$ be given with
coordinates
$a_{1}=(-\frac{C}{2}/\frac{\sqrt{3}C}{2}),a_{2}=(-\frac{C}{2}/-\frac{\sqrt{3}C}{2}),a_{3}=(C/0)$.
They form an equilateral triangle with sidelength $\sqrt{3}C$. The placement
is sketched above. The diameter of this set is equal to the length of one side
of the triangle which is larger than $C$ but smaller than $2C$. The optimal
solution to (Bar$(\mathcal{A})$) is $\xi=(0/0)$ with
$\mathcal{Z}^{\ast}=3C=f_{C}(\xi)$. But for $\eta=(-\frac{C}{2}/0)$ we get
$f_{C}(\eta)=(\sqrt{3}+1)C<f_{C}(\xi)$. Therefore $\xi\in\mathcal{X}^{\ast}$
but $\xi\not\in\mathcal{X}_{C}^{\ast}$. (Optimal solutions to
(Bar${}_{C}(\mathcal{A})$) would be each of the points $a_{1}$ to $a_{3}$ with
$\mathcal{Z}^{\ast}_{C}=2C$.)

######  Example 5.

[Example where (b) is not true for $q=2$, $d=\ell_{2}$ and
$\sqrt{C}<\operatorname{diam}(\mathcal{A})\leq 2\sqrt{C}$] Take the same
situation as in Example 4, but for simplicity set $C=1$. The diameter of this
set is equal to the length of one side of the triangle which is
$\sqrt[2]{3}\approx 1.732$ and therefore smaller than $2$. The optimal
solution to (Bar$(\mathcal{A})$) is $\xi=(0/0)$ with
$\mathcal{Z}^{\ast}=3=f_{C}(\xi)$. But for $\eta=\left(-\frac{1}{2}/0\right)$
we get
$f_{C}(\eta)=\left(2\cdot\left(\frac{\sqrt{3}}{2}\right)^{2}+1\right)=\frac{5}{2}<f_{C}(\xi)$.
Therefore $\xi\in\mathcal{X}^{\ast}$ but $\xi\not\in\mathcal{X}_{C}^{\ast}$.

We remark that in the last three examples above we have
$f(\xi^{\ast})=f_{C}(\xi^{\ast})$ for the (respective) optimal solution
$\xi^{\ast}$ to (Bar$(\mathcal{A})$) but still
$\xi^{\ast}\not\in\mathcal{X}^{\ast}_{C}$, i.e., this solution is not optimal
for (Bar${}_{C}(\mathcal{A})$).

In the following table we summarize the results for metrics $d$ and $q\geq 1$:

| $\operatorname{diam}(\mathcal{A})\leq\sqrt[q]{C}$ | $\sqrt[q]{C}<\operatorname{diam}(\mathcal{A})\leq 2\sqrt[q]{C}$ | $\operatorname{diam}(\mathcal{A})>2\sqrt[q]{C}$
---|---|---|---
$(a)\ \mathcal{Z}^{\ast}=\mathcal{Z}^{\ast}_{C}$ | holds if (conv), | may or may not hold, | never for $q=1$,
| see Thm 17 | see Examples 2 to 5 | never for $q>1$ for $\ell_{p}$-norms,
|  |  | see Thm 16
$(b)\ \mathcal{X}^{\ast}\subseteq\mathcal{X}^{\ast}_{C}$ | holds if (conv), | may or may not hold, | may or may not hold,
| follows from Lem 14 | see Examples 2 to 5 | see Examples 1 and 3

Furthermore, we have seen in Theorem 13 that (a) and (b) are always true if
$2r_{0}\leq\sqrt[q]{C}$, where $r_{0}$ is the radius of a smallest ball $B$
such that $\mathcal{X}^{\ast}(A)\cap B\neq\emptyset$ for all
$A\subseteq\mathcal{A}$.

For a very small cutoff $C$ relative to the distances between the points of
$\mathcal{A}$ and for a large cutoff compared to the diameter of $\mathcal{A}$
we can say something about the optimal solutions to
(Bar${}_{C}(\mathcal{A})$):

######  Lemma 18.

Let $\xi^{\ast}$ be an optimal solution to (Bar${}_{C}(\mathcal{A})$).

  * (i)

If $C<\frac{1}{2^{q}}\underset{a_{1}\neq
a_{2}\in\mathcal{A}}{\min}d^{q}(a_{1},a_{2})$ we have
$\xi^{\ast}\in\mathcal{A}$ and $|{\rm active}(\xi^{\ast})|=1$.

  * (ii)

If $\sqrt[q]{C}\geq 2\cdot\operatorname{diam}(\mathcal{A})$ we have $|{\rm
active}(\xi^{\ast})|=n$, implying $\mathcal{Z}^{\ast}=\mathcal{Z}^{\ast}_{C}$
and $\mathcal{X}^{\ast}=\mathcal{X}^{\ast}_{C}$.

###### Proof.

  * (i)

We show that there is no better barycenter than a point $a\in\mathcal{A}$. The
cutoff is smaller than the shortest distance between two points of
$\mathcal{A}$. Therefore for any $a\in\mathcal{A}:$
$f_{C}(a,\mathcal{A})=(n-1)\cdot C$.
Suppose $|{\rm active}_{C}(a)|=1$ and there is a point
$\xi\in\mathbb{R}^{k}:f_{C}(\xi,\mathcal{A})<(n-1)\cdot C$, then $|{\rm
active}(\xi)|\geq 2$. Take two different points $a_{1},a_{2}\in{\rm
active}(\xi)$. Then $d(a_{1},\xi)+d(\xi,a_{2})\geq
d(a_{1},a_{2})>2\sqrt[q]{C}$. Therefore one of the distances
$d(a_{1},\xi),d(\xi,a_{2})$ is larger than $\sqrt[q]{C}$ and thus one of the
distances $d^{q}(a_{1},\xi),d^{q}(\xi,a_{2})$ is larger than $C$. This
contradicts the assumption that both points are in ${\rm active}(\xi)$.

  * (ii)

We prove that if $|{\rm active}(\xi^{\ast})|<n$, then $\xi^{\ast}$ is not
optimal for (Bar${}_{C}(\mathcal{A})$). Suppose $|{\rm
active}(\xi^{\ast})|<n$. Then there is a point $a_{1}\in\mathcal{A}$ such that
$d^{q}(\xi^{\ast},a_{1})>C\geq 2^{q}\cdot\operatorname{diam}(\mathcal{A})^{q}$
and therefore

$d(\xi^{\ast},a_{1})>2\cdot\operatorname{diam}(\mathcal{A}).$

Thus for any $a\in\mathcal{A}$

$d(\xi^{\ast},a)\geq\underbrace{d(\xi^{\ast},a_{1})}_{>2\operatorname{diam}(\mathcal{A})}-\underbrace{d(a_{1},a)}_{\leq\operatorname{diam}(\mathcal{A})}>\operatorname{diam}(\mathcal{A}).$

We know now that for all $a\in\mathcal{A}$:
$d^{q}(\xi^{\ast},a)\geq\operatorname{diam}(\mathcal{A})^{q}$. Therefore
$f_{C}(\xi^{\ast})\geq
n\cdot\operatorname{diam}(\mathcal{A})^{q}>(n-1)\cdot\operatorname{diam}(\mathcal{A})^{q}\geq
f_{C}(a_{1})$, which means $\xi^{\ast}$ is not optimal for
(Bar${}_{C}(\mathcal{A})$).

Thus under the conditions of $(ii)$ we do have $|{\rm active}(\xi^{\ast})|=n$.
So we know that $\xi^{\ast}$ is a barycenter of all points in $\mathcal{A}$
and therefore an optimal solution to (Bar$(\mathcal{A})$) with
$\mathcal{Z}^{\ast}_{C}=f_{C}(\xi^{\ast})=f(\xi^{\ast})=\mathcal{Z}^{\ast}$.
Since $\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$ was arbitrary, we obtain
$\mathcal{X}^{\ast}_{C}\subseteq\mathcal{X}^{\ast}$ and Lemma 14 implies
$\mathcal{X}^{\ast}\subseteq\mathcal{X}^{\ast}_{C}$, hence
$\mathcal{X}^{\ast}=\mathcal{X}^{\ast}_{C}$.

∎

##  5 Comparing BarC with BarC,α

From an applied point of view it might be interesting to consider the empty
barycenter as a valid solution. The barycenter of a set of points is
representative for said set. Having no barycenter can then be interpreted as
”the points are so widely spread, that no single point represents them”.

After solving (Bar${}_{C}(\mathcal{A})$) it is easy to check if the empty
barycenter is a better solution. But it would save computation time if we knew
before the calculations that the empty barycenter _must_ be better. In this
section we compare (Bar${}_{C}(\mathcal{A})$) with
(Bar${}_{C,\alpha}(\mathcal{A})$) and work out criteria under which we know
that either the empty barycenter is the optimal solution to
(Bar${}_{C,\alpha}(\mathcal{A})$) or that the empty barycenter cannot be the
optimal solution.
If the empty barycenter is not the best solution to
(Bar${}_{C,\alpha}(\mathcal{A})$) we know that the points of $\mathcal{A}$
must contain a cluster which has a certain _density_. That means that there
must exist a subset $A\subseteq\mathcal{A}$ with $\operatorname{diam}(A)\leq
2\sqrt[q]{C}$ containing at least $(1-\alpha)\cdot n$ points:

######  Lemma 19.

The empty barycenter is an optimal solution if there is no ball $B$ with
radius $\sqrt[q]{C}$ that contains more than $(1-\alpha)\cdot n$ points.

###### Proof.

Suppose such a ball does not exist. Let $\xi^{\ast}\in\mathbb{R}^{k}$ be an
optimal solution to (Bar${}_{C,\alpha}(\mathcal{A})$). We know for all
$a\in{\rm active}(\xi^{\ast})$ that $d(\xi^{\ast},a)\leq\sqrt[q]{C}$.
Therefore there exists a ball $B$ with radius $\sqrt[q]{C}$ that contains all
points of ${\rm active}(\xi^{\ast})$ and no points of ${\rm
const}(\xi^{\ast})$. Since, by assumption, $B$ can not contain more than
$(1-\alpha)\cdot n$ points, we know that ${\rm active}(\xi^{\ast})$ does not
contain more than $(1-\alpha)\cdot n$ points, i.e., $|{\rm
active}(\xi^{\ast})|\leq(1-\alpha)\cdot n$. But then $|{\rm
const}(\xi^{\ast})|\geq n-(1-\alpha)\cdot n=\alpha\cdot n$. So the points in
${\rm const}(\xi^{\ast})$ alone contribute at least $\alpha\cdot C\cdot
n=f_{C,\alpha}(\emptyset,\mathcal{A})$ to
$f_{C,\alpha}(\xi^{\ast},\mathcal{A})$, hence
$f_{C,\alpha}(\xi^{\ast},\mathcal{A})\geq\alpha\cdot C\cdot
n=f_{C,\alpha}(\emptyset,\mathcal{A})$. If
$\emptyset\notin\mathcal{X}^{\ast}_{C,\alpha}$, then
$f_{C,\alpha}(\xi^{\ast},\mathcal{A})<\alpha\cdot C\cdot n$, which contradicts
the optimality of $\xi^{\ast}$. ∎

In Lemma 19 we could argue with ${\rm active}(\xi^{\ast})$ alone. If $|{\rm
active}(\xi^{\ast})|\leq(1-\alpha)\cdot n$, then the empty barycenter is an
optimal solution. But we do not know $\xi^{\ast}$ and therefore ${\rm
active}(\xi^{\ast})$ before solving (Bar${}_{C}(\mathcal{A})$). Checking if
such a ball exists might in general be computationally more easy than solving
(Bar${}_{C}(\mathcal{A})$). E.g. for data in $\mathbb{R}^{2}$ and the
Euclidean distance, i.e. $d=\ell_{2}$, $q=1$, it can be checked in
$\mathcal{O}(n^{2})$ time if such a ball exists, see [chazelle1986circle].

We further improve Algorithm 2 by using the empty barycenter as an upper bound
on the optimal solution to (Bar${}_{C,\alpha}(\mathcal{A})$). For the empty
barycenter we know directly the value
$f_{C,\alpha}(\emptyset,\mathcal{A})=n\cdot\alpha\cdot C$ and initialize the
algorithm with this value as current best solution.

Input : Set $\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}$, cutoff $C>0$, $\alpha>0$

Output : A barycenter $\xi^{\ast}$ of $\eqref{empty}$, objective function
value $\mathcal{Z}_{C,\alpha}^{\ast}$

1 Set $\xi^{\ast}\leftarrow\emptyset$,
$\mathcal{Z}_{C,\alpha}^{\ast}\leftarrow n\cdot\alpha\cdot C$,
$\mathcal{B}\leftarrow\mathcal{A}$;

2 for  _$i\leftarrow 1$ to $(n-1)$_ do

3 $continue$ $\leftarrow$ $true$;

4 $m\leftarrow|\\{a\in\mathcal{B}\ |\ d^{q}(a_{i},a)\leq 2^{q}C\\}|$;

5 if  _$(n-m)\cdot C\geq\mathcal{Z}_{C,\alpha}^{\ast}$_ then

6 $\mathcal{B}\leftarrow\mathcal{B}\setminus\\{a_{i}\\}$;

7 $continue$ $\leftarrow$ $false$;

8

9 end if

10 if  _continue_ then

11 Inner Loop;

12

13 end if

14

15 end for

return _$\xi^{\ast},\mathcal{Z}_{C,\alpha}^{\ast}$_

Algorithm 3 Second improvement of Algorithm 1

######  Theorem 20.

Let $\mathcal{A}\subseteq\mathbb{R}^{2}$, let $d$ be a norm-metric and say we
can solve (Bar$(\mathcal{A})$) in $h(n)$ time. Then Algorithm 3 solves the
problem (Bar${}_{C}(\mathcal{A})$) in $\mathcal{O}(n^{2}\cdot h(n))$ time.

###### Proof.

The runtime and the correctness of the algorithm follow directly from the
proof of Theorem 9. Formally, the only difference is that Algorithm 3 is
initialized with the empty barycenter as the current best solution. ∎

Compared with Algorithm 2 we replace the initial $\xi^{\ast}$ in the
declaration from $\xi^{\ast}\leftarrow a_{1}$ with
$\xi^{\ast}\leftarrow\emptyset$. This is of course only better, if
$f_{C,\alpha}(\emptyset,\mathcal{A})\leq f_{C}(a_{1},\mathcal{A})$, which
implies $\alpha\leq\frac{n-1}{n}$, compare Lemma 3. We will see in the
following Lemma that for $\alpha$ close enough to $1$, the empty barycenter
cannot be an optimal solution to (Bar${}_{C,\alpha}(\mathcal{A})$):

######  Lemma 21.

If $\alpha>\frac{n-1}{n}$ then the empty barycenter is never an optimal
solution.

###### Proof.

Referring to Lemma 3 we compare $f_{C,\alpha}(\emptyset,\mathcal{A})$, with
$\alpha>\frac{n-1}{n}$, to the upper bound of $\mathcal{Z}_{C}^{\ast}$:
$f_{C,\alpha}(\emptyset,\mathcal{A})=\alpha\cdot n\cdot C>\frac{n-1}{n}\cdot
n\cdot C=(n-1)\cdot C\geq\mathcal{Z}^{\ast}_{C}$.
Hence a point $\xi^{\ast}\in\mathbb{R}^{k}$ exists, such that
$f_{C}(\xi^{\ast},\mathcal{A})<f_{C,\alpha}(\emptyset,\mathcal{A})$. ∎

To determine if the empty barycenter is a better solution than any solution in
$\mathbb{R}^{k}$ before solving $\eqref{cutoff}$, we can look at the pairwise
distances between the points of $\mathcal{A}$.

If the points of $\mathcal{A}$ are close to each other compared to $C$, it is
more likely that the cost of an empty barycenter exceeds the cost of a
solution in $\mathbb{R}^{k}$. If on the other hand the points are far apart,
it is more likely that the empty barycenter is optimal. We define the _mean
pairwise distance_ between points of $\mathcal{A}$ and study its relation to
the optimal solution of (Bar${}_{C,\alpha}(\mathcal{A})$) w.r.t $n,\alpha$ and
$C$.

######  Definition 22.

Let $\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}\subseteq\mathbb{R}^{k}$. We define
the _mean pairwise distance_

$\displaystyle\operatorname{mpd}(\mathcal{A}):=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j=1}^{n}d^{q}_{C}(a_{i},a_{j})=\frac{2}{n(n-1)}\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}d^{q}_{C}(a_{i},a_{j}).$

The following statements are immediately clear.

######  Lemma 23.

We always have

  * •

$0\leq\operatorname{mpd}(\mathcal{A})\leq C$,

  * •

$0\leq\operatorname{mpd}(\mathcal{A})\leq\operatorname{diam}(\mathcal{A})^{q}$.

The mean pairwise distance can be computed in $\mathcal{O}(n^{2})$ time. If it
is ‘small’ compared to the cutoff $C$ and $\alpha$ and $n$, we know that the
empty barycenter can again not be an optimal solution to
(Bar${}_{C,\alpha}(\mathcal{A})$). Let us hence study
$\operatorname{mpd}_{C}(\mathcal{A}):=\frac{1}{C}\operatorname{mpd}(\mathcal{A})\in[0,1]$
as percentage of $C$. We can strengthen Lemma 21 as follows:

######  Lemma 24.

If $\alpha>\operatorname{mpd}_{C}(\mathcal{A})\cdot\frac{n-1}{n}$, then for at
least one point
$a\in\mathcal{A}:f_{C,\alpha}(a,\mathcal{A})<f_{C,\alpha}(\emptyset,\mathcal{A})$,
i.e. the empty barycenter is never an optimal solution.

###### Proof.

Suppose such a point $a$ does not exist. We show that then
$\operatorname{mpd}_{C}(\mathcal{A})\cdot\frac{n-1}{n}>\alpha$: For any
$i\in\\{1,\ldots,n\\}$:
$\sum_{j=1}^{n}d_{C}^{q}(a_{i},a_{j})=f_{C,\alpha}(a_{i},\mathcal{A})>f_{C,\alpha}(\emptyset,\mathcal{A})=\alpha\cdot
C\cdot n$. The mean pairwise distance then is

$\displaystyle\operatorname{mpd}(\mathcal{A})$
$\displaystyle=\frac{1}{n(n-1)}\sum_{i=1}^{n}\sum_{j=1}^{n}d^{q}_{C}(a_{i},a_{j})$
$\displaystyle>\frac{1}{n(n-1)}\sum_{i=1}^{n}\alpha\cdot C\cdot
n=\frac{1}{n(n-1)}\cdot\alpha\cdot C\cdot n^{2}=\alpha\cdot
C\cdot\frac{n}{n-1},$

hence $\operatorname{mpd}_{C}(\mathcal{A})\cdot\frac{n-1}{n}>\alpha$. ∎

We can directly transfer this result to the diameter
$\operatorname{diam}(\mathcal{A})$ which we used in Section 4, since the mean
pairwise distance is never larger than the diameter raised to the power $q$.

######  Corollary 25.

If $\alpha>\frac{\operatorname{diam}(\mathcal{A})^{q}}{C}\cdot\frac{n-1}{n}$
then the empty barycenter is never an optimal solution.

###### Proof.

From $\alpha>\frac{\operatorname{diam}(\mathcal{A})^{q}}{C}\cdot\frac{n-1}{n}$
it follows that $\alpha>\operatorname{mpd}_{C}\cdot\frac{n-1}{n}$. With Lemma
24 we know that then the emtpy barycenter is not an optimal solution to
(Bar${}_{C,\alpha}(\mathcal{A})$). ∎

We can reformulate Lemma 24 and Corollary $25$ to get a condition for the
diameter and the mean pairwise distance for the empty barycenter not being
optimal: $\operatorname{mpd}(\mathcal{A})<\alpha\cdot C\cdot\frac{n}{n-1}$ or
$\operatorname{diam}(\mathcal{A})^{q}<\alpha\cdot C\cdot\frac{n}{n-1}$ then
$\emptyset$ is not optimal.

On the other hand we show that for small $\alpha$ the empty barycenter is
always an optimal solution to (Bar${}_{C,\alpha}(\mathcal{A})$):

######  Lemma 26.

If
$\alpha\leq\min\left\\{\frac{1}{2^{q}}\frac{\operatorname{diam}(\mathcal{A})^{q}}{n\cdot
C},\frac{1}{n}\right\\}$ then the empty barycenter is an optimal solution to
(Bar${}_{C,\alpha}(\mathcal{A})$).

###### Proof.

Let $\xi^{\ast}\in\mathcal{X}^{\ast}_{C}$ be an optimal solution to
(Bar${}_{C}(\mathcal{A})$). We know from the triangle inequality that there
exists a point $a\in\mathcal{A}$ such that
$d(\xi^{\ast},a)\geq\frac{1}{2}\operatorname{diam}(\mathcal{A})$. Therefore
$d_{C}^{q}(\xi^{\ast},a)\geq\min\\{\frac{1}{2^{q}}\operatorname{diam}(\mathcal{A})^{q},C\\}$
and hence
$\mathcal{Z}_{C}^{\ast}\geq\min\\{\frac{1}{2^{q}}\operatorname{diam}(\mathcal{A})^{q},C\\}$.
Then

$\displaystyle f_{C,\alpha}(\emptyset,\mathcal{A})$
$\displaystyle=n\cdot\alpha\cdot
C\leq\min\left\\{\frac{1}{2^{q}}\operatorname{diam}(\mathcal{A})^{q},C\right\\}$
$\displaystyle\Leftrightarrow\alpha$
$\displaystyle\leq\min\left\\{\frac{1}{2^{q}}\frac{\operatorname{diam}(\mathcal{A})^{q}}{n\cdot
C},\frac{1}{n}\right\\}$

∎

######  Remark.

When $\operatorname{diam}(\mathcal{A})\geq 2C$ then
$\min\left\\{\frac{1}{2^{q}}\frac{\operatorname{diam}(\mathcal{A})^{q}}{n\cdot
C},\frac{1}{n}\right\\}=\frac{1}{n}$. And thus for $\alpha\leq\frac{1}{n}$ and
$\operatorname{diam}(\mathcal{A})\geq 2C$ the empty barycenter is an optimal
solution to (Bar${}_{C,\alpha}(\mathcal{A})$).

The following lemma and example show that for larger
$\operatorname{mpd}(\mathcal{A})$ both cases,
$\emptyset\in\mathcal{X}^{\ast}_{C,\alpha}$ or
$\emptyset\not\in\mathcal{X}^{\ast}_{C,\alpha}$, are possible.

######  Lemma 27.

Let $\alpha=\frac{1}{2},q=1$. Then for any $\varepsilon>0$ there exists a set
$\mathcal{A}\subseteq\mathbb{R}^{k}$ such that
$\operatorname{mpd}(\mathcal{A})=\frac{1}{2}\cdot C+\varepsilon$, but where
$f_{C,\frac{1}{2}}(\emptyset,\mathcal{A})<f_{C,\frac{1}{2}}(x,\mathcal{A})$
for any $x\in\mathbb{R}^{k}$.

###### Proof.

We construct a set $\mathcal{A}=\\{a_{1},\ldots,a_{2n}\\}\subseteq\mathbb{R}$,
where $n>\frac{C}{4\varepsilon}+\frac{1}{2}$ and set
$\delta:=\frac{2n(2n-1)\varepsilon-nC}{4(n-1)}$. The points have the
coordinates
$a_{1}=-\delta,a_{2}=\ldots=a_{n}=0,a_{n+1}=\ldots=a_{2n-1}=C,a_{2n}=C+\delta$.
Then
$\operatorname{mpd}(\mathcal{A})=\frac{n^{2}C+2(n-1)\delta}{n(2n-1)}=\frac{nC}{2n-1}+\frac{2(n-1)\delta}{n(2n-1)}=\frac{C}{2}+\frac{C}{2(2n-1)}+\frac{2(n-1)\delta}{n(2n-1)}$.With
the specified $\delta$ we have
$\operatorname{mpd}(\mathcal{A})=\frac{C}{2}+\varepsilon$ and since
$n>\frac{C}{4\varepsilon}+\frac{1}{2}$ we have $\delta>0$.

An optimal solution of (Bar${}_{C}(\mathcal{A})$) is any of the points
$a_{2},\ldots a_{2n-1}$. The optimal objective function value
$\mathcal{Z}^{\ast}_{C}=f_{C,\frac{1}{2}}(a_{2},\mathcal{A})=nC+\delta$ is
larger than $nC=f_{C,\frac{1}{2}}(\emptyset,\mathcal{A})$. So the empty
barycenter is a better solution than the best solution in $\mathbb{R}$.

∎

We have seen in Lemma 24 that for $\operatorname{mpd}(\mathcal{A})<\alpha\cdot
C\cdot\frac{n}{n-1}$ the empty barycenter is not optimal. Yet, Lemma 27 proves
that the $\operatorname{mpd}$ can be arbitrarily close to $\alpha\cdot C$ and
still the empty barycenter _is_ an optimal solution. The following example
proves on the other hand that there exist sets with an $\operatorname{mpd}$
arbitrarily close to $C$, for which the empty barycenter is _not_ an optimal
solution.

######  Example 6.

[Example for large $\operatorname{mpd}(\mathcal{A})$ where
$\emptyset\not\in\mathcal{X}^{\ast}_{C,\alpha}$ for $\alpha\geq\frac{1}{2}$.]

Let two points in $\mathbb{R}$ be given,
$a_{1}=0,a_{2}=\sqrt[q]{C-\varepsilon}$ for some $\varepsilon>0$. Now
$f_{C,\alpha}(a_{1},\mathcal{A})=C-\varepsilon<C\leq 2\cdot\alpha\cdot
C=f_{C,\alpha}(\emptyset,\mathcal{A})$.

Note that the situation of this example is the same if we replace the
$\operatorname{mpd}$ by the _minimum_ or _median_ distance between points,
since both values are $C-\varepsilon$.

We finally summarize our findings. We know that the empty barycenter _is_ an
optimal solution to (Bar${}_{C,\alpha}(\mathcal{A})$) if

  * •

there is no ball $B$ with radius $\sqrt[q]{C}$ that contains at least
$(1-\alpha)\cdot n$ points, see Lemma 19,

  * •

$\alpha\leq\min\left\\{\frac{1}{2^{q}}\frac{\operatorname{diam}(\mathcal{A})^{q}}{n\cdot
C},\frac{1}{n}\right\\}$, see Lemma 26.

On the other hand we know that the empty barycenter _is not_ an optimal
solution if

  * •

$\alpha>\frac{n-1}{n}$, see Lemma 21,

  * •

$\alpha>\operatorname{mpd}_{C}(\mathcal{A})\cdot\frac{n-1}{n}$ or
$\alpha>\frac{\operatorname{diam}(\mathcal{A})^{q}}{C}\cdot\frac{n-1}{n}$, see
Lemma 24 and the subsequent Corollary.

In the other cases we do not know in advance if the empty barycenter is
optimal, c.f. Lemma 27 and Example 6.

##  6 Sensitivity analysis w.r.t $C$

So far we have assumed that the cutoff value $C$ is a priori specified, but
there is a wide range of scenarios where this is not the case.

In the application described in Section 7 we often (but not always) know the
order of magnitude of a reasonable cutoff $C$ due to the physical reality of
the data, but this typically still leaves a large interval of possible choices
which may lead to very different outcomes.

In a more direct location problem setting the actual $C$ may be determined by
another player trying to maximize her profit based on knowledge of the entire
function $g=[C\mapsto\min_{\xi}f_{C}(\xi,\mathcal{A})]$ (or
$[C\mapsto\min_{\xi}f_{C,\alpha}(\xi,\mathcal{A})]$, where we still assume
$\alpha>0$ to be fixed). Taking up the waste dump example from the
introduction, it may be that in the decision process the local transportation
company is asked for the price $C$, at which it would offer to transport
domestic waste to the dump. A profit maximizing choice of $C$ depends on
detailed knowledge of the function $g$.

This function is what we study in the present section.

######  Definition 28.

Let $x\in\mathbb{R}^{k}$ be a fixed point. Define the two functions

  * (i)

$g_{x}:\mathbb{R}_{+}\rightarrow\mathbb{R},C\mapsto f_{C}(x,\mathcal{A})$

  * (ii)

$g:\mathbb{R}_{+}\rightarrow\mathbb{R},C\mapsto
f_{C}(\mathcal{A}):=\underset{\xi\in\mathbb{R}^{k}}{\min}\
f_{C}(\xi,\mathcal{A})$.

The function $g_{x}$ maps the cutoff $C$ to the objective function value
$f_{C}(x,\mathcal{A})$, while the function $g$ maps the cutoff to the
_optimal_ objective function value $\mathcal{Z}_{C}^{\ast}$, compare with
(Bar${}_{C}(\mathcal{A})$).

We study how the barycenter $\xi^{\ast}=\xi^{\ast}_{C}$ and the values of
$g_{x}$ and $g$ change with changing $C$.

######  Example 7.

[Example for discontinuity of the optimal solution to
(Bar${}_{C}(\mathcal{A})$) w.r.t $C$]

$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$

Let $5$ points in $\mathbb{R}$ be given,
$a_{1}=0,a_{2}=0.5,a_{3}=5,a_{4}=6,a_{5}=7$. Consider $q=1$ and $d=|\cdot|$.
The location of the points is sketched above. The following gives a complete
description of $\mathcal{X}^{\ast}_{C}$ for various $C$. Note that at the
boundaries of the ranges the union of the barycenters in the lower and the
higher range are in $\mathcal{X}^{\ast}_{C}$. For $0\leq C\leq 0.5$ any of the
points $a_{1}$ to $a_{5}$ is optimal for (Bar${}_{C}(\mathcal{A})$). For
$0.5\leq C\leq 1.5$ any point on the interval $[a_{1},a_{2}]$ is optimal, for
$1.5\leq C\leq 5.25$ $a_{4}$ is optimal, for $5.25\leq C$ $a_{3}$, the
barycenter of the problem without cutoff, is optimal.

As seen in the example, the optimal solution set for
(Bar${}_{C}(\mathcal{A})$) can change abruptly in $C$. On the other hand we
will see that $g$, i.e. the objective function $C\mapsto f_{C}(\mathcal{A})$
is quite well-behaved and can be computed efficiently.

######  Lemma 29.

Let $x\in\mathbb{R}^{k}$ be some fixed point,
$\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}\subseteq\mathbb{R}^{k}$. Sort the points
increasingly by their distance to $x$ and define $d_{i}:=d^{q}(x,a_{i})$, so
that $d_{1}\leq d_{2}\leq\ldots\leq d_{n}$. Then the function $g_{x}$ is

  * (i)

of the form

$g_{x}(C)=\sum_{i=1}^{j}d_{i}+(n-j)\cdot C,\ \text{ with }j=|{\rm
active}_{C}(x)|$ (6)

$g_{x}$ is therefore piecewise linear with kinks in $d_{i}$.

  * (ii)

continuous,

  * (iii)

non-decreasing,

  * (iv)

concave.

###### Proof.

(i) W.l.o.g we assume that $x\neq a_{i}$ for all $i\in\\{1,2,\ldots,n\\}$.
Otherwise we eliminate the first $j$ points from our list, where
$j:=\max\\{i\in\\{1,\ldots,n\\}\ |\ d_{i}=0\\}$, use $n^{\prime}=n-j$ in the
proof and re-enumerate $a_{j+1},\ldots,a_{n}$ to
$a_{1},\ldots,a_{n^{\prime}}$.
By definition

$\displaystyle
g_{x}(C)=f_{C}(x,\mathcal{A})=\sum_{i=1}^{n}\text{min}\\{d_{i},C\\}.$

We can split this sum into sums over indices of active and constant points, as
defined in Section 3. Let $m=m_{C}=|{\rm active}_{C}(x)|$. Then
$d_{1}\leq\ldots\leq d_{m_{C}}\leq C$ and $C<d_{m_{C}+1}\leq\ldots\leq d_{n}$
and

$\displaystyle
g_{x}(C)=\sum_{i=1}^{n}\text{min}\\{d_{i},C\\}=\sum_{i=1}^{m_{C}}d_{i}+\sum_{i=m_{C}+1}^{n}C=\sum_{i=1}^{m_{C}}d_{i}+(n-m_{C})\cdot
C.$

For any $j\in\\{1,\ldots,n\\}$ the sum over the $d_{i}$ is constant for
$d_{j}\leq C<d_{j+1}$ so $g_{x}$ is piecewise linear. The slope of the $j$-th
line segments is $(n-j)$.
(ii) We know that $g_{x}$ is piecewise linear with kinks in $d_{i}$. On these
line segments, i.e. $d_{i}<C<d_{i+1}$, the function is continuous. We have to
check for the kinks of $g_{x}$, i.e. $C=d_{j}$ for some $j$, if the two line
segments for $C=d_{j}-\varepsilon$ and $C=d_{j}+\varepsilon$, $\varepsilon>0$,
intersect at $g_{x}(d_{j})$.

Take $j\in\\{1,\ldots,n\\}$. For $d_{j-1}<C<d_{j}$:
$g_{x}(C)=\sum_{i=1}^{j-1}d_{i}+\sum_{i=j}^{n}C$. For $j=1$ the first sum is
$0$. For $d_{j}<C<d_{j+1}$: $g_{x}(C)=\sum_{i=1}^{j}d_{i}+\sum_{i=j+1}^{n}C$.
For $j=n$ the second sum is $0$.

For $C=d_{j}$:
$\sum_{i=1}^{j-1}d_{i}+\sum_{i=j}^{n}C=\sum_{i=1}^{j-1}d_{i}+d_{j}+\sum_{i=j+1}^{n}C=\sum_{i=1}^{j}d_{i}+\sum_{i=j+1}^{n}C$.
So the two line segments intersect and therefore is $g_{x}$ continuous.
(iii) Take two cutoffs $C_{1}<C_{2}$. Since $C_{1}<C_{2}$ we also have
$\text{min}\\{d_{i},C_{1}\\}\leq\text{min}\\{d_{i},C_{2}\\}$ for all
$i\in\\{1,\ldots,n\\}$. Now
$g_{x}(C_{1})=\sum_{i=1}^{n}\text{min}\\{d_{i},C_{1}\\}\leq\sum_{i=1}^{n}\text{min}\\{d_{i},C_{2}\\}=g_{x}(C_{2})$,
so $g_{x}$ is non-decreasing.
(iv) With larger $C$ the cardinality $m_{C}$ of ${\rm active}_{C}(x)$
increases. Therefore the slope $(n-m_{C})$ of the line segments decreases with
growing $C$, so $g_{x}$ is also concave. ∎

We can now extend the results for $g_{x}$ which hold for all
$x\in\mathbb{R}^{k}$ to the function $g$.

######  Theorem 30.

The function $g$ is continuous, non-decreasing and concave.

###### Proof.

For calculating the function $g$ we need to solve (Bar${}_{C}(\mathcal{A})$)
for every $C$. For a fixed $C$ an optimal solution to $\eqref{cutoff}$ is a
solution of (Bar$(\mathcal{A})$) for some subset $A\subseteq\mathcal{A}$,
compare Lemma 5.

Since $\mathcal{A}$ is finite, there are only finitely many subsets of
$\mathcal{A}$. There is therefore only a finite set $S$ of candidates for an
optimal solution to (Bar${}_{C}(\mathcal{A})$). The function $g$ is the
minimum of the functions $g_{\xi}$, i.e. $g(C)=\min_{\xi\in S}g_{\xi}(C)$.

The minimum of finitely many continuous functions is continuous. The same
holds for the properties “non-decreasing” and “concave”. ∎

Recall the piecewise linear form of the function $g_{x}$. The function $g$ as
minimium of finitely many piecewise linear functions is then itself piecewise
linear. The slopes of the line segments are given by the cardinalities of the
sets ${\rm active}_{C}(\xi^{\ast})$ for optimal solutions
$\xi^{\ast}=\xi^{\ast}_{C}\in\mathcal{X}^{\ast}_{C}$ for the different $C$.
Those slopes are integers between $n-1$ and $0$. Since $g$ is continuous and
concave the function consists of at most $n$ linear pieces. The slope only
changes at the kinks of the function $g$. And only there does the cardinality
of the set ${\rm active}(\xi^{\ast})$ change. Let us say we have kinks at
$C_{1}<C_{2}$ and no kinks in between. Let $C\in(C_{1},C_{2})$. Any solution
$\xi^{\ast}_{C}\in\mathcal{X}^{\ast}_{C}$ defines the same function
$g_{\xi^{\ast}_{C}}$ on the interval $(C_{1},C_{2})$. The function $g$ has its
next kink at $C_{2}$, so $C_{2}$ is the smallest value greater than $C_{1}$
where any of the functions $g_{\xi^{\ast}_{C}}$ can have a kink. It follows
that any solution $\xi^{\ast}_{C}\in\mathcal{X}^{\ast}_{C}$ is optimal on the
whole interval $[C_{1},C_{2}]$.
But that means if we find all values $C$ at which $g$ has a kink, and a
corresponding optimal solution $\xi^{\ast}$ for each of those $C$, we have an
optimal solution to (Bar${}_{C}(\mathcal{A})$) and the value of $g$ for any
$0\leq C<\infty$.

We describe in Algorithm 4 how we can calculate these optimal solutions
$\xi^{\ast}$ and values of $g$ in at most $n-1$ steps, by finding the
different line segments. The function $\mathtt{bar}(C,\mathcal{A})$ calculates
an optimal solution $\xi^{\ast}$ of (Bar${}_{C}(\mathcal{A})$) and the
corresponding value $\mathcal{Z}^{\ast}_{C}$ for a given cutoff $C$.
$\mathtt{bar}(\infty,\mathcal{A})$ returns an optimal solution to
(Bar$(\mathcal{A})$).
Let the set $\mathcal{S}\subseteq\\{0,\ldots,n-1\\}$ contain the _slopes_ of
the line segments that we have already found and the set
$\mathfrak{O}\subseteq\\{0,\ldots,n-1\\}\setminus\mathcal{S}$ the slopes of
the segments that we still might find, the _open_ slopes. Each of the lines
$l_{n-1},\ldots,l_{0}$ is defined by a point $(C,\mathcal{Z}^{\ast}_{C})$ and
the slope $i$, which is indicated by its index. The algorithm will calculate
(up to) $n$ different lines. These lines are tangents for the function $g$. By
calculating the intersection points of lines $l_{i}$ and $l_{i+1}$ we get the
kinks of $g$ and thereby the complete function $g(C)$, which is a combination
of segments of the lines $l_{n-1},\ldots,l_{0}$.

Input : The set $\mathcal{A}=\\{a_{1},\ldots,a_{n}\\}$

Output : The function $g(C)$ and up to $n-1$ barycenters corresponding to the
different values of $C$.

1 Set $\mathcal{S}\leftarrow\\{0,n-1\\}$,
$\mathfrak{O}\leftarrow\\{1,\ldots,n-2\\}$;

2
$(\xi^{\ast}_{0},\mathcal{Z}^{\ast}_{0})\leftarrow\mathtt{bar}(\infty,\mathcal{A})$,
$(\xi^{\ast}_{n-1},\mathcal{Z}^{\ast}_{n-1})\leftarrow(a_{1},0)$;

3 Define the lines $l_{0}$ by the point $(0,\mathcal{Z}^{\ast}_{0})$ and the
slope $0$ and $l_{n-1}$ by the point $(0,0)$ and the slope $n-1$ ;

4 while  _$\mathfrak{O}\neq\emptyset$_ do

5 Take smallest index $o$ from $\mathfrak{O}$;

6 Take the largest $i\in\mathcal{S}:i<o$ and the smallest
$j\in\mathcal{S}:o<j$;

7 Calculate the intersection point $(C,y)$ of lines $l_{i}$ and $l_{j}$;

8
$(\xi^{\ast}_{C},\mathcal{Z}^{\ast}_{C})\leftarrow\mathtt{bar}(C,\mathcal{A})$
;

9 if  _$\mathcal{Z}_{C}^{\ast}=y$_ then

10 $\mathfrak{O}\leftarrow\mathfrak{O}\setminus\\{i+1,i+2,\ldots,j-1\\}$;

11

12 end if

13 else

14 Set $m\leftarrow|{\rm active}(\xi^{\ast}_{C})|$,
$\xi^{\ast}_{n-m}\leftarrow\xi^{\ast}_{C}$,
$\mathcal{Z}^{\ast}_{n-m}\leftarrow\mathcal{Z}_{C}^{\ast}$;

15 Define $l_{n-m}$ by the point $(C,\mathcal{Z}^{\ast}_{n-m})$ and slope
$n-m$;

16 $\mathfrak{O}\leftarrow\mathfrak{O}\setminus\\{n-m\\}$;

17 $\mathcal{S}\leftarrow\mathcal{S}\cup\\{n-m\\}$;

18

19 end if

20

21 end while

22for  _$i\in\mathcal{S}\setminus\\{n-1\\}$_ do

23 $j\leftarrow\min\\{k\in\mathcal{S}\ |\ k>i\\}$;

24 Calculate the intersection point $(C_{i},g(C_{i}))$ of lines $l_{i}$ and
$l_{j}$;

25

26 end for

27$(C_{n-1},g(C_{n-1}))\leftarrow(0,0)$;

return _$\\{(C_{i},g(C_{i}))\ |\ i\in\mathcal{S}\\}$ ,
$\\{\xi^{\ast}_{i}|i\in\mathcal{S}\\}$_

Algorithm 4 Calculate $f_{C}(\mathcal{A})$ for all $C$

######  Theorem 31.

Say we can solve (Bar${}_{C}(\mathcal{A})$) in $h_{C}(n)$ time. Then Algorithm
4 computes the function $g$ in $\mathcal{O}(n\cdot h_{C}(n))$ time.

###### Proof.

We have to prove two things: first the runtime and second the correctness.
First: The function $\mathtt{bar}(C,\mathcal{A})$ is called at most $n-1$
times. Once in line $2$ and once in every iteration of the while-loop, lines
$4$ to $18$. The while-loop is called at most $n-2$ times. The computation of
the (at most) $n-1$ intersection points in line $19$ to $22$ is done in
$\mathcal{O}(n)$ time. Together we have a runtime of $\mathcal{O}(n\cdot
h_{C}(n)+n)=\mathcal{O}(n\cdot h_{C}(n))$.
Second: We know by Lemma 29 that $g$ starts in $(0,0)$ with slope $n-1$ and
will eventually get constant, taking the value
$g(C)=\mathcal{Z}^{\ast}_{0}=\mathtt{bar}(\infty,\mathcal{A})$. So the lines
$l_{0}$ and $l_{n-1}$ defined in line $3$ contain the outermost line segments
of $g$ and bound $g$ above due to its concavity.
We have to prove that the algorithm finds all line segments in between.
Suppose we have two line segments $l_{i}$ and $l_{j}$. Now we compute the
intersection of those lines in line $7$. We know that this intersection point
$(C,y)$ must lie on or above $g$ by concavity. We now calculate the value
$\mathcal{Z}_{C}^{\ast}$ for this $C$ and get a point
$(C,\mathcal{Z}_{C}^{\ast})$ that is on $g$. There are two possibilities:

  * •

Either $y=\mathcal{Z}_{C}^{\ast}$, which means the intersection point of the
lines _is_ already on $g$. But that means that the function $g$ can have no
line segments with slopes between $i$ and $j$, so all these values are removed
from the set $\mathfrak{O}$ in line $10$.

  * •

Or we found a point on $g$ that is below the intersection point $(C,y)$. For
the found barycenter $\xi^{\ast}$ we look at the cardinality $m$ of ${\rm
active}(\xi^{\ast})$. The slope of the line $l_{n-m}$, which is a tangent on
$g$, is given by the _non_ -active points. So the next line $l_{n-m}$ is given
by the slope $n-m$ and the point $(C,\mathcal{Z}_{c}^{\ast})$. This line is
saved and we add $n-m$ to $\mathcal{S}$ and delete $n-m$ from $\mathfrak{O}$.

So with every iteration of lines $4$ to $18$ we either find out that $l_{i}$
and $l_{j}$ intersect on $g$ or we find one new line segment that is a tangent
for $g$. The function $g$ is uniquely defined by these tangents. ∎

Note that Algorithm 4 can be parallelized. When the intersection of two lines
is calculated in line $7$, the problem can then be split into a subproblem to
the left of this point and to the right of this point.

######  Remark.

Having computed $g$, the function $g^{(\alpha)}:\mathbb{R}_{+}\to\mathbb{R}$,
$C\mapsto\min_{\xi\in\mathbb{R}^{k}\cup\\{\emptyset\\}}f_{C,\alpha}(\xi,\mathcal{A})$
is easily derived, since $g^{(\alpha)}(C)=\min\\{g(C),\alpha\cdot n\cdot
C\\}$. Provided that $\alpha<\frac{n-1}{n}$, which means $\alpha\cdot n$ is
smaller than the initial slope of $g$, we obtain from the concavity of $g$ and
the fact that it must eventually be constant, that there is exactly one
$C_{0}>0$ where the graph of $g$ intersects with the linear function
$[C\mapsto\alpha\cdot n\cdot C]$. We then have $g^{(\alpha)}(C)=\alpha\cdot
n\cdot C$ to the left of $C_{0}$ and $g^{(\alpha)}(C)=g(C)$ to the right of
$C_{0}$. If $\alpha\geq\frac{n-1}{n}$, we have $g^{(\alpha)}=g$ everywhere.

##  7 Applications

The original motivation for investigating (Bar${}_{C,\alpha}(\mathcal{A})$)
comes from [muller2020metrics], where two of the current authors studied
barycenters of finite collections of point patterns for their use as summary
statistics. We briefly describe here the relevant details, because we think
that the involved concepts and their algorithmic implications may well be of
interest in the context of location problems where e.g. an optimal supply
chain is to be maintained to a number of companies that each have several
branch offices.

For the present purpose we define a point pattern as a finite subset of
$\mathbb{R}^{k}$ and denote the set of all such patterns by $\mathfrak{N}$.
Then for given point patterns $\xi_{1},\ldots,\xi_{m}\in\mathfrak{N}$, a
barycenter is any minimizer of the Fréchet functional

$F(\zeta)=\sum_{j=1}^{m}\tau(\xi_{j},\zeta)^{q}$ (7)

over $\zeta\in\mathfrak{N}$. Here $\tau$ is the transport-transform (TT)
metric on $\mathfrak{N}$ introduced in [muller2020metrics]. Basically,
$\tau(\xi_{j},\zeta)^{q}$ is the minimal “cost” of matching a subset of
$\xi_{j}$ and a subset of $\zeta$, where each pairing of a point $x\in\xi_{j}$
and a point $z\in\zeta$ incurs a cost of $d(x,z)^{q}$ and each unmatched point
of either pattern incurs a cost of $\frac{1}{2}C$.

If we consider point patterns as discrete measures by identifying
$\xi=\\{x_{1},\ldots,x_{n}\\}$ with $\sum_{i=1}^{n}\delta_{x_{i}}$ for
pairwise distinct $x_{i}$, we can re-interpret the TT metric as a special case
of an unbalanced Wasserstein metric, see [chizat2018scaling] for the
definition of the latter or [muller2020metrics], Remark 3, for the full
argument.

Intuitively, a barycenter can be thought of as a “typical” representative, in
a sense an “average point pattern” that reflects common properties of the data
point patterns. In [muller2020metrics] barycenters were applied to point
patterns of crime locations in two cities, with the goal of detecting
systematic differences over the years or between different seasons. Another
goal might be for planning the efficient deployment of police officers
according to the time of the day (or year) and maybe other side constraints
(predictive policing).

[borgwardt2021computational] prove that the computation of a sparse
Wasserstein barycenter is $\mathcal{NP}$-hard for three point patterns with
the same number of points in $\mathbb{R}^{2}$ and $q=2$. In the authors’
setting the barycenter can be a more general discrete finite measure (not
necessarily with unit weights), but their sparseness condition limits the
number of support points. There does not seem to be a direct theoretical
result for our problem (7), but based on the current state of theoretical and
applied research, we assume that this problem is insolvable for all practical
purposes. Therefore [muller2020metrics] proposed a heuristic algorithm based
on an equivalent form of the TT metric: First fill up the point patterns
$\xi_{1},\ldots,\xi_{m}$ so that they all have the same cardinality $n$, say,
by adding points at a single “virtual” location $\aleph\not\in\mathbb{R}^{k}$
at distance $(\frac{1}{2}C)^{1/q}$ apart from any locations in
$\mathbb{R}^{k}$. For $\xi_{j}=\\{x_{j1},\ldots,x_{jn}\\}$ and
$\zeta=\\{z_{1},\ldots,z_{n}\\}$ (multisets since they may include $\aleph$
several times), we may then express the metric $\tau$ equivalently as

$\tau(\xi_{j},\zeta)^{q}=\min_{\pi\in
S_{n}}\sum_{i=1}^{n}d^{\prime}(x_{ji},z_{\pi(i)})^{q},$ (8)

where $S_{n}$ denotes the set of permutations on $\\{1,\ldots,n\\}$ and

$d^{\prime}(x,z)^{q}=\begin{cases}\min\bigl{\\{}d(x,z)^{q},C\\}&\text{if
$x,z\in\mathbb{R}^{k}$};\\\ \frac{1}{2}C&\text{if $\aleph\in\\{x,z\\}$, $x\neq
z$};\\\ 0&\text{if $x=z=\aleph$};\end{cases}$ (9)

see [muller2020metrics], Theorem 1. We may then find a local optimum of the
Fréchet functional (7) by alternating between forming pairwise disjoint
clusters of the form $\mathcal{C}=\\{x_{1,i_{1}},\ldots,x_{m,i_{m}}\\}$,
$i_{1},\ldots,i_{m}\in\\{1,\ldots,n\\}$, including exactly one (maybe virtual)
point from each data pattern via optimal matching, and computing suitable
“centers” for each such cluster $\mathcal{C}$ by minimizing

$f(z)=\sum_{j=1}^{m}d^{\prime}(x_{j,i_{j}},z)^{q}$ (10)

over $z\in\mathbb{R}^{k}\cup\\{\aleph\\}$. In the algorithm of
[muller2020metrics] this minimization was only performed approximately, using
some crude but fast heuristics. However, except for the fact that
$x_{j,i_{j}}=\aleph$ may hold for individual $j$, the minimization (10)
corresponds to problem (Bar${}_{C,\alpha}(\mathcal{A})$) with
$\alpha=\frac{1}{2}$. Noting that the contribution from $x_{j,i_{j}}=\aleph$
is constant as long as $z\in\mathbb{R}^{k}$, we may therefore use a slightly
adapted version of Algorithm 3 to compute the centers exactly.

##  8 Simulation study

For comparing Drezners algorithm with the two improvements Algorithm 2 and
Algorithm 3 , we created six test scenarios of point patterns inside the unit
square and compared runtimes and solutions of the algorithm. For scenarios (1)
to (5) we chose rectangles and generated the coordinates of the points inside
each rectangle uniformly at random, independently of one another. In scenario
(2) to (5) we combined two of those rectangles. The number of points in every
rectangle follows a Poisson distribution with parameters chosen in such a way
that the expected number of points is $600$ in each scenario. The scenarios
are (from left to right, top to bottom):

  * (1)

one unit square

  * (2)

two squares with edge length $0.5$ that overlap in a square of size $0.1\times
0.1$, half of the points in each square

  * (3)

one small square with edge length $0.4$ inside the unit square, half of the
points in each square

  * (4)

one small square with edge length $0.3$ inside the unit square, half of the
points in each square

  * (5)

two rectangles overlapping on one strip of width $0.2$. Height for both
rectangles is $0.5$, width $0.5$ and $0.6$, half of the points in each
rectangle

  * (6)

$4$ small clusters with background noise. The clusters are two-dimensional
Gaussians with $\sigma=0.025$. The cluster centers are uniformly drawn for
each pattern individually. The expected number of points in the clusters is
$90\%$, an expected number of $10\%$ are uniformly drawn in the unit square.

We ran a simulation study with $100$ patterns from each scenario to compare
the three algorithms. The results are in Table 1. As expected, all three
algorithms find the exact solution every time.
In these calculations we set $\alpha=0.5$, so the cost of an empty barycenter
is $C\cdot\frac{|\mathcal{A}|}{2}$. We have $d=\ell_{2}$ and $q=2$. For the
computation we used the publicly available R-package ttbary, see [ttbary].
The runtime depends highly on the point pairs from which barycenter candidates
are calculated. The larger the cutoff $C$, the more point pairs are taken into
account and barycenter candidates have to be checked. Therefore the runtime
gets higher with larger cutoff. For Algorithm 1 for the smallest cutoff
$C=0.01$ the runtime is about $4-12$ seconds for the $100$ patterns combined.
In Scenario $6$ the runtime for $C=0.01$ is about $81$ seconds for the $100$
runs, because even with the small cutoff due to the small clusters many
barycenter candidates have to be calculated. For all the scenarios the runtime
goes up to $1709-2574$ seconds for $C=0.3$. We also counted how many
barycenter candidates had to be calculated by this algorithm in total for each
scenario. In Table 1 we compare the runtime of the two improved Algorithms 2
and 3 to the ‘original’ runtime and compare how many barycenter candidates
could be skipped by the improved algorithms.
The column ‘skipped points’ presents for each scenario and cutoff the
_relative_ number of barycenter candidates that were skipped by this
algorithm.
The values correspond to Algorithm 2/Algorithm 3/Algorithm 1 (first and second
improvement and original algorithm). For example in Scenario $1$, $C=0.01$ the
$0.450/1.000/0$ means that Algorithm 2 was able to skip $45\%$ of the
barycenter candidates, Algorithm 3 skipped $100\%$ of the barycenter
candidates, and of course Algorithm 1 skipped nothing.
Similarly the column ‘time’ presents for each scenario and cutoff the
_relative_ time the algorithms took for the $100$ point patterns compared to
the runtime of the original Algorithm 1. For example in Scenario $1$, $C=0.01$
the $0.702/0.252/1$ means that Algorithm 2 was about $30\%$ faster and
Algorithm 3 was about $75\%$ faster than Algorithm 1.

We can clearly see the connection between the amount of skipped barycenter
candidates and the amount of time that is saved. The first improvement,
Algorithm 2, is almost never slower than the original algorithm and can for
smaller cutoffs $C$ save up to $30\%$ of the runtime. The second improved
version, Algorithm 3, is much faster than the other two. The empty barycenter
is in these scenarios for small cutoffs always the optimal solution. For
cutoffs up to $C=0.1$ almost all point pairs can be skipped a priori. In
scenario $1$ even for $C=0.2$ the runtime is below $1\%$ of the runtime of the
original algorithm.

| Scenario 1 |  | Scenario 2 |  | Scenario 3 |
---|---|---|---|---|---|---
$C=$ | skipped points | time | skipped points | time | skipped points | time
$0.01$ | 0.450/1.000/0 | 0.702/0.252/1 | 0.383/1.000/0 | 0.703/0.144/1 | 0.289/1.000/0 | 0.778/0.133/1
$0.02$ | 0.273/1.000/0 | 0.773/0.082/1 | 0.128/1.000/0 | 0.911/0.044/1 | 0.105/1.000/0 | 0.911/0.038/1
$0.03$ | 0.094/1.000/0 | 0.940/0.040/1 | 0.027/1.000/0 | 0.970/0.020/1 | 0.087/1.000/0 | 0.917/0.018/1
$0.05$ | 0.006/1.000/0 | 0.999/0.015/1 | 0.004/1.000/0 | 0.992/0.008/1 | 0.081/1.000/0 | 0.922/0.007/1
$0.075$ | 0.001/1.000/0 | 1.005/0.007/1 | 0.001/1.000/0 | 1.001/0.004/1 | 0.073/1.000/0 | 0.931/0.003/1
$0.1$ | 0.000/1.000/0 | 1.005/0.004/1 | 0.000/1.000/0 | 1.001/0.002/1 | 0.064/1.000/0 | 0.938/0.002/1
$0.2$ | 0.000/0.995/0 | 1.002/0.006/1 | 0.000/0.762/0 | 1.000/0.239/1 | 0.049/0.287/0 | 0.953/0.716/1
$0.3$ | 0.000/0.263/0 | 1.000/0.738/1 | 0.000/0.009/0 | 1.001/0.991/1 | 0.018/0.041/0 | 0.983/0.960/1
| Scenario 4 |  | Scenario 5 |  | Scenario 6 |
$C=$ | skipped points | time | skipped points | time | skipped points | time
$0.01$ | 0.189/1.000/0 | 0.854/0.095/1 | 0.397/1.000/0 | 0.683/0.125/1 | 0.056/1.000/0 | 0.954/0.012/1
$0.02$ | 0.071/1.000/0 | 0.952/0.026/1 | 0.137/1.000/0 | 0.886/0.036/1 | 0.023/1.000/0 | 0.979/0.004/1
$0.03$ | 0.070/1.000/0 | 0.945/0.012/1 | 0.044/1.000/0 | 0.963/0.017/1 | 0.012/1.000/0 | 0.990/0.002/1
$0.05$ | 0.072/1.000/0 | 0.933/0.005/1 | 0.008/1.000/0 | 0.993/0.006/1 | 0.015/1.000/0 | 0.986/0.002/1
$0.075$ | 0.076/1.000/0 | 0.926/0.002/1 | 0.004/1.000/0 | 0.999/0.003/1 | 0.080/0.987/0 | 0.920/0.014/1
$0.1$ | 0.079/0.981/0 | 0.925/0.021/1 | 0.002/1.000/0 | 0.998/0.002/1 | 0.181/0.953/0 | 0.820/0.048/1
$0.2$ | 0.116/0.231/0 | 0.887/0.772/1 | 0.000/0.171/0 | 1.000/0.831/1 | 0.127/0.528/0 | 0.875/0.473/1
$0.3$ | 0.028/0.032/0 | 0.972/0.968/1 | 0.000/0.000/0 | 1.001/1.000/1 | 0.042/0.132/0 | 0.960/0.870/1
Table 1: Comparison of the runtime of the two improved Algorithms 2 and 3 to
the ‘original’ runtime of Algorithm 1 and how many barycenter candidates were
skipped by the improved algorithms. The column ‘skipped points’ presents for
each scenario and cutoff the _relative_ number of barycenter candidates that
were skipped by this algorithm. The values correspond to Algorithm 2/Algorithm
3/Algorithm 1 (first and second improvement and original algorithm). Similarly
the column ‘time’ presents for each scenario and cutoff the _relative_ time
the algorithms took for the $100$ point patterns compared to the runtime of
the original Algorithm 1.

###  8.1 Consequences for the barycenter algorithm of [muller2020metrics]

As mentioned in Section 7 problem 10, that stems from [muller2020metrics], is
identical to (Bar${}_{C,\alpha}(\mathcal{A})$) with $\alpha=\frac{1}{2}$. In
the algorithm of [muller2020metrics] this problem was solved by a fast
heuristic:
Starting with a point $x\in\mathbb{R}^{k}$ we calculate ${\rm active}(x)$,
solve Bar$({\rm active}(x))$ with optimal solution $\xi^{\ast}$ and set
$x\leftarrow\xi^{\ast}$. The heuristic uses the idea that is proven in Lemma
5, that the optimal solution of (Bar${}_{C}(\mathcal{A})$) must be an optimal
solution of (Bar) for some subset of $\mathcal{A}$. With this heuristic the
objective function value cannot increase, since the distances to ${\rm
active}(x)$ are optimized and the distances to ${\rm const}(x)$ cannot
increase by definition of ${\rm const}(x)$.

An implementation of the original algorithm of [muller2020metrics] can be
found in the publicly available R package ttbary, [ttbary]. We implemented
Algorithm 3 in the algorithm of [muller2020metrics] to replace the heuristic.
In a simulation study we compared the implementation in [ttbary] with our
version in which the heuristic is replaced with Algorithm 3.

It turned out that doing the exact calculation instead of the heuristic for
solving problem 10 does not improve the algorithm of [muller2020metrics] in
general. In the algorithm the size of $\mathcal{A}$ in
(Bar${}_{C,\alpha}(\mathcal{A})$) depends on the number of point patterns. The
set $\mathcal{A}$ consists of exactly one point (including $\aleph$, see
Section 7) of every pattern. We compared the runtime and the resulting
objective function value (cost) of the computed pseudo-barycenters. For the
three ‘groupsizes’ of $20$, $50$ and $100$ point patterns per group we created
$600$ groups each. Both algorithms had the same input for each of the $1800$
groups. In our tests about half of the costs with the exact solutions of
problem 10 were smaller and half of the costs were larger compared to the
heuristic. At the same time the runtime for the algorithm with the exact
subroutine for 10 is about $3.5$, $13.5$ or $42$ times larger for the
groupsizes of $20$, $50$ and $100$ respectively. Since the heuristic is a lot
faster and does not yield a worse solution we recommend to stay with the
original version of the algorithm as it is presented in [muller2020metrics].

##  9 Discussions and outlook

In this paper we presented the problems (Bar$(\mathcal{A})$), also known as
the Weber-problem, and the extension (Bar${}_{C}(\mathcal{A})$), which is
related to a problem studied by [drezner1991facility]. Additionally we
introduced the new barycenter problem (Bar${}_{C,\alpha}(\mathcal{A})$), where
we extend the classic problem by the option to have an empty solution. In
Sections 4 and 5 we investigated under which conditions an optimal solution of
(Bar$(\mathcal{A})$) is also an optimal solution to (Bar${}_{C}(\mathcal{A})$)
or (Bar${}_{C,\alpha}(\mathcal{A})$). We also investigated under which
conditions an optimal solution to (Bar$(\mathcal{A})$) cannot be an optimal
solution to (Bar${}_{C}(\mathcal{A})$) or (Bar${}_{C,\alpha}(\mathcal{A})$).
Most results are based solely on the geometric structure of the dataset, like
the diameter of the set or the mean pairwise distance between its points. The
summaries of the results can be found in Table 4 and the statements thereafter
and at the end of Section 5.

For the average problem we typically do not know if we can reduce
(Bar${}_{C}(\mathcal{A})$) or (Bar${}_{C,\alpha}(\mathcal{A})$) to
(Bar$(\mathcal{A})$). We presented two improvements of the algorithm
introduced by [drezner1991facility] to solve (Bar${}_{C}(\mathcal{A})$) and
(Bar${}_{C,\alpha}(\mathcal{A})$) more efficiently. We furthermore gave an
algorithm for solving (Bar${}_{C}(\mathcal{A})$) simultaneously for _all_
$C\geq 0$ by solving $\mathcal{O}(n)$ problems of type
(Bar${}_{C}(\mathcal{A})$) for specified values of $C$.

For future research it might be interesting to generalize the improved
algorithms to the original problem stated by [drezner1991facility], who
allowed different cutoffs for every point.

Another interesting topic is to find new criteria to determine beforehand if
solving (Bar$(\mathcal{A})$) is sufficient. Another algorithmic idea is to
split the original problem into subproblems that can be solved independently,
where one optimal solution of the subproblems is guaranteed to be the optimal
solution of the original problem. One could also study how
(Bar${}_{C}(\mathcal{A})$) simplifies for special cases like the
$\ell_{1}$-metric, where we can optimize separately over the $k$ dimensions.
These findings could help to solve the problems (Bar${}_{C}(\mathcal{A})$) and
(Bar${}_{C,\alpha}(\mathcal{A})$) faster in the future.

Input :

MSS˙Location˙problems.bbl