# Two trees are better than one 111Research partially supported by the
Hungarian Science Foundation (NKFIH) grant K-131529, the ERC grant no. 882971,
”GeoScape,” and by the Erdős Center.

Adrian Dumitrescu222Algoresearch L.L.C., Milwaukee, WI 53217, USA, E-mail:
<EMAIL_ADDRESS>János Pach333Alfréd Rényi Institute of
Mathematics, Budapest, Hungary. Email<EMAIL_ADDRESS>Géza Tóth444Alfréd Rényi
Institute of Mathematics, Budapest, Hungary. Email<EMAIL_ADDRESS>
###### Abstract

We consider partitions of a point set into two parts, and the lengths of the
minimum spanning trees of the original set and of the two parts. If $w(P)$
denotes the length of a minimum spanning tree of $P$, we show that every set
$P$ of $n\geq 12$ points admits a bipartition $P=R\cup B$ for which the ratio
$\frac{w(R)+w(B)}{w(P)}$ is strictly larger than $1$; and that $1$ is the
largest number with this property. Furthermore, we provide a very fast
algorithm that computes such a bipartition in $O(1)$ time and one that
computes the corresponding ratio in $O(n\log{n})$ time.

In certain settings, a ratio larger than $1$ can be expected and sometimes
guaranteed. For example, if $P$ is a set of $n$ random points uniformly
distributed in $[0,1]^{2}$ ($n\to\infty$), then for any $\varepsilon>0$, the
above ratio in a maximizing partition is at least $\sqrt{2}-\varepsilon$ with
probability tending to $1$. As another example, if $P$ is a set of $n$ points
with spread at most $\alpha\sqrt{n}$, for some constant $\alpha>0$, then the
aforementioned ratio in a maximizing partition is $1+\Omega(\alpha^{-2})$.

All our results and techniques are extendable to higher dimensions.

##  1 Introduction

A _Euclidean minimum spanning tree_ (EMST), for a set of $n$ points in the
Euclidean plane or Euclidean space is a spanning tree of the $n$ points that
has the minimum total length (the length of a tree edge is the Euclidean
distance between its endpoints). Write $w(P)$ for the length of an EMST of
$P$. Motivated by a question of Cultrera et al. [9, 10] arising from their
work on chromatic alpha shapes and persistence, we study the following
problem. For a finite set $P$ of $n$ points in the plane, and a bipartition
$P=R\cup B$ into red and blue points, consider the ratio

$\frac{w(R)+w(B)}{w(P)}.$ (1)

Call the maximum, over all non-trivial bipartitions of $P$ into two sets, the
_max MST-ratio_ of $P$, denoted $\gamma(P)$. For $n=3,4,5$ we exhibit examples
for which the ratios are at most $1$ and we have no larger examples with this
property. As such, we are tempted to conjecture that perhaps $6$ points
suffice to guarantee a bipartition whose MST-sum strictly exceeds the MST
length of the set itself, see Conjecture 1 below. We come close to answering
this question, see our Theorem 3 below.

######  Conjecture 1.

For any set $P$ of $n\geq 6$ points in the plane we have $\gamma(P)>1$.

We first show using graph theoretic arguments that if $|P|=n\geq 3$, the
maximum ratio $\gamma(P)$ is at least $\frac{n-2}{n-1}$. Note that this lower
bound tends to $1$ as $n\to\infty$. On the other hand, for any $n\geq 4$ and
$\varepsilon>0$, there exists a set of $n$ points in the plane with
$\gamma(P)\leq 1+\varepsilon$. Therefore, the constant $1$ cannot be replaced
by larger constant in Conjecture 1. For $n=3$, there exists $P$ such that
$\gamma(P)=1/2$, and for $n=4$, there exists $P$ such that
$\gamma(P)=\frac{\sqrt{3}+1}{3}=0.910\ldots$; see Fig. 1.

Figure 1: A point set $P$ with $\gamma(P)=\frac{\sqrt{3}+1}{3}=0.910\ldots$.

######  Proposition 2.

Let $P$ be any set of $n\geq 3$ points in the plane.

Then $\gamma(P)\geq\frac{n-2}{n-1}$. On the other hand, for any $n\geq 3$ and
$\varepsilon>0$, there exists $P$ with $|P|=n$, such that $\gamma(P)\leq
1+\varepsilon$.

The example showing the second statement was also found by Cultrera et al.
[10]. Using geometric arguments, we can improve the first statement and settle
Conjecture 1, for $n\geq 12$.

######  Theorem 3.

For any set $P$ of $n\geq 12$ points in the plane, we have $\gamma(P)>1$.

A suitable bipartition with a ratio $>1$ can be computed in $O(1)$ time,
whereas the corresponding ratio can be computed in $O(n\log{n})$ time.

We also prove sharper lower bounds on $\gamma(P)$ in two cases: (i) for random
points uniformly distributed in a square (or any other fat container region),
and (ii) for dense point sets. In both cases we require the number of points
to be sufficiently large. Note that neither class of point-sets includes the
other. The proofs are simpler than that of Theorem 3.

We start with random points uniformly distributed. According to a classic
result of Beardwood, Halton, and Hammersley [3], the length of a minimum
spanning tree of a random sample $\\{X_{1},\ldots,X_{n}\\}$ of $n$ points
uniformly distributed in the unit cube $[0,1]^{k}$ satisfies

${L(X_{1},\ldots,X_{n})/n^{1-1/k}}\to\beta(k)$ (2)

with probability one, where $\beta(k)>0$ is a constant depending on $k$.
Later, Bertsimas and Van Ryzin [5] proved that
${\beta(k)/\sqrt{k}}\to{1/\sqrt{2\pi\mathrm{e}}}$, see also [23]; however,
this more precise determination will not be needed here. Using only (2) we
prove:

######  Theorem 4.

Let $P$ be a set of $n$ random points uniformly distributed in $[0,1]^{2}$.

Then for any $\varepsilon>0$, we have $\gamma(P)\geq\sqrt{2}-\varepsilon$ with
probability tending to $1$ as $n\to\infty$.

We continue with dense point sets. For a set $P$ of $n$ points in the plane,
define

$\Delta(P)=\frac{\max\\{{\rm dist}(a,b):a,b\in P,a\neq b\\}}{\min\\{{\rm
dist}(a,b):a,b\in P,a\neq b\\}},$

where ${\rm dist}(a,b)$ is the Euclidean distance between points $a$ and $b$.
The ratio $\Delta(P)$ is referred to as the _aspect ratio_ or the _spread_ of
$P$; see for instance [2]. We assume without loss of generality that the
minimum pairwise distance is $1$ and in this case $\Delta(P)$ is the diameter
${\rm diam}(P)$ of $P$. A standard volume argument shows that if $P$ has $n$
points, then $\Delta(P)\geq c\,n^{1/2}$, where $c>0$ is an absolute constant.
If $n$ is large enough, then $c\geq 2^{1/2}3^{1/4}\pi^{-1/2}\approx 1.05$; see
[24, Prop. 4.10]. An $n$-element point set satisfying the condition
$\Delta(P)\leq\alpha\,n^{1/2}$, for some constant $\alpha>0$, is called here
$\alpha$-_dense_ ; see [25] or [6, Ch. 10].

######  Theorem 5.

Let $P$ be a dense set of $n$ points in the plane, with $\Delta(P)\leq\alpha
n^{1/2}$, for some $\alpha\geq 2^{1/2}3^{1/4}\pi^{-1/2}$.

Then $\gamma(P)\geq 1+\Omega(\alpha^{-2})$. More precisely, we have

$\gamma(P)\geq 1+\frac{1}{11(2\alpha+1)^{2}},\;\;\;\text{ for large }n.$

#### Related work.

Graph decomposition is a classical topic in graph theory [8, 12, 22]. In this
note, we are interested in finding partitions of a points set into two parts
such that the total length of their MST’s is as large as possible.

Estimating the length of a shortest tree or tour of $n$ points in the unit
square with respect to Euclidean distances has been studied as early as 1940s
and 1950s by Fejes Tóth [13], Few [15], and Verblunsky [26], respectively.
Clustering algorithms based on minimum and maximum spanning trees have been
studied by Asano et al. [1].

In the same spirit, recall that the well-know _Euclidean Steiner ratio_ is the
infimum over all finite point sets $P$ in the plane of the ratio between the
lengths of a shortest Steiner tree and that of minimum spanning tree of the
set [17, 7]. Denoting this ratio by $\rho$, Gilbert and Pollak conjectured in
1968 that $\rho\geq\sqrt{3}/2=0.866\ldots$. Early results due to Graham and
Hwang [18] and Du and Hwang [11] showed that $\rho\geq 1/\sqrt{3}\approx
0.577$, and $\rho\geq 0.8$. The current best lower bound on this ratio,
$\rho\geq\rho_{0}$, is due to Chung and Graham [7]; here
$\rho_{0}=0.824168\ldots$ is the unique real root in the interval $(0.8,1)$ of
a polynomial of $12$th
degree555$P(x)=x^{12}-4x^{11}-2x^{10}+40x^{9}-31x^{8}-72x^{7}+116x^{6}+16x^{5}-151x^{4}+80x^{3}+56x^{2}-64x+16$..

For every $n\geq 7$, there exists a set $P$ of $n$ points such that
$\gamma(P)$ can get arbitrarily close to $\frac{2\sqrt{3}+3}{3}\approx 2.154$.
Using the above lower bound on the Steiner ratio, Cultrera et al. [10] proved
that if $P$ is any set of $n\geq 3$ points in the plane, then $\gamma(P)\leq
2/\rho_{0}\approx 2.426$.

##  2 Preliminaries

We subsequently assume that $n\geq 3$, since otherwise the maximum MST-ratio
is $0$. We first observe the following upper bounds for $n=3,4,5$.

When $n=3$, the three vertices of an equilateral triangle $P$ give
$\gamma(P)=1/2$. Indeed, by symmetry the three possible bipartitions yield the
same lengths, $1$, whereas the MST length is $2$. Proposition 2 shows that
this bound is the best possible.

When $n=4$, let $P$ be the four vertices of a rhombus of unit side-length and
an angle of $60^{\circ}$. The bipartition that gives the maximum ratio is one
with $|R|=|B|=2$, where $R$ is a diametral pair, thus
$\gamma(P)=\frac{\sqrt{3}+1}{3}\approx 0.910$. It can be checked that if $P$
consists of the four vertices of a square, then the maximum ratio is slightly
larger, $\gamma(P)=\frac{2\sqrt{2}}{3}\approx 0.942$. Proposition 2 yields
that $\gamma(P)\geq 2/3$, for $|P|=4$.

When $n=5$, let $P$ consist of the following five points (written as complex
numbers): $0,1,\omega,\omega^{2},\omega^{3}$, where
$\omega=\cos\frac{\pi}{3}+i\sin\frac{\pi}{3}$ is the $6$th root of unity. It
is easy to check that the bipartition that gives the maximum ratio is one with
$R=\\{1,\omega^{3}\\}=\\{-1,1\\}$, and so $\gamma(P)=\frac{2+2}{4}=1$.
Proposition 2 yields that $\gamma(P)\geq 3/4$, for any point set $P$ with
$|P|=5$.

#### Disjoint disks.

Let $P$ be a finite set of points in $\mathbb{R}^{d}$. Let
$\mathcal{D}(P)=\\{\omega(p)\colon p\in P\\}$, where $\omega(p)$ is the
largest closed ball centered at $p$ and containing no other points from $P$ in
its interior. Given $p\in P$, let $r(p)$ denote the radius of $\omega(p)$.

A set of points $P$ in $\mathbb{R}^{d}$ is said to satisfy the _disjoint
balls_ property if $\mathcal{D}(P)$ contains two disjoint balls. For the
plane, we use the term _disjoint disks_ property. A key (easy) observation
about this property is its monotonicity.

######  Observation 6.

Let $P$ be a set of points in the plane that satisfies the disjoint disks
property. If $P\subset Q$, then $Q$ also satisfies this property.

###### Proof.

Assume that $\omega(p)$ and $\omega(p^{\prime})$ are disjoint, where
$p,p^{\prime}\in P$. Adding the points in $Q\setminus P$ maintains this
property, since the disks centered at $p$ and $p^{\prime}$ can only get
smaller. ∎

######  Lemma 7.

Let $P$ be a set of points in the plane that satisfies the disjoint disks
property.

Then there exist two points $p,q\in P$ such that $|pq|>r(p)+r(q)$.

###### Proof.

Let $p,q\in P$ be the centers of two disjoint disks in $\mathcal{D}(P)$. Then
$p,q$ clearly satisfy the requirement. ∎

According to a result of Kézdy and Kubicki [21], any set of $n\geq 12$ points
in the plane satisfies the _disjoint disks_ property; we record this fact in
the following lemma. On the other hand, this property cannot be guaranteed for
any set of $8$ points; and it is conjectured that it holds for any set of
$n\geq 9$ points [16, 19].

######  Lemma 8.

(Kézdy and Kubicki [21]) Let $P$ be a set of $n$ points in the plane with
$n\geq 12$.

Then $P$ satisfies the disjoint disks property.

#### Proof of Proposition 2.

_Upper bound._ Take $p_{1}=(0,0)$, $p_{n}=(1,0)$, and the rest of points in
the interval $(0,\varepsilon/n)$. It is easily verified that $w=1$, and
$w_{1}+w_{2}\leq 1+\varepsilon$: indeed, the point $p_{n}$ appears only in one
tree, whereas the length of the second tree is less than $\varepsilon$, which
yields

$\gamma(P)=\frac{w_{1}+w_{2}}{w}\leq 1+\varepsilon,$

as required.

_Lower bound._ Let $T_{0}$ be an MST of $P$, with $w=|T_{0}|$ and

$\gamma(P)=\frac{w_{1}+w_{2}}{w},$

where $w_{1}+w_{2}$, where $w_{1}$ and $w_{2}$ are the lengths of the MSTs,
say, $T_{1}$ and $T_{2}$, for the red and the blue points in a bipartition of
_maximum_ length. We claim that $w_{1}+w_{2}\geq\frac{n-2}{n-1}\,w$. Indeed,
consider the bipartition $P=R\cup B$ obtained by deleting the shortest edge,
say, $e$, of $T_{0}$. Note that $T_{0}\setminus\\{e\\}$ consists of two
spanning trees $T_{R}$ and $T_{B}$, of $R$ and $B$, respectively. Moreover,
$T_{R}$ and $T_{B}$ are MSTs of $R$ and $B$, respectively. Indeed, assume for
contradiction that there is spanning tree $T^{\prime}_{R}$ of $R$ with a
smaller length than $T_{R}$, i.e., $|T^{\prime}_{R}|<|T_{R}|$. Then
$T^{\prime}_{R}\cup\\{e\\}\cup T_{B}$ is a spanning tree of $P$ of length

$|T^{\prime}_{R}|+|e|+|T_{B}|<|T_{R}|+|e|+|T_{B}|=w,$

a contradiction. Similarly, there is no spanning tree $T^{\prime}_{B}$ of $B$
with a smaller length than $T_{B}$.

Since $T$ has $n-1$ edges, we have $|e|\leq w/(n-1)$. The length of the
resulting bipartition in terms of spanning trees is at least

$w-\frac{w}{n-1}=\frac{n-2}{n-1}\,w.$

Since $w_{1}+w_{2}$ is the length of a maximum bipartition (in the same
terms), we have

$w_{1}+w_{2}\geq\frac{n-2}{n-1}\,w,$

as claimed. Consequently,

$\gamma(P)=\frac{w_{1}+w_{2}}{w}\geq\frac{n-2}{n-1},$

as required. ∎

###  2.1 Key lemmas

The following lemmas can be formulated for general graphs; however, here we
restrict ourselves to the simpler geometric setting.

######  Lemma 9.

Let $T$ be a minimum spanning tree of a complete geometric graph $G=K_{n}(P)$,
and $p,q\in P$ be the centers of two disjoint disks in $\mathcal{D}(P)$.

Then $w(P\setminus\\{p,q\\})\geq w-r(p)-r(q)$, where $w=w(P)$.

###### Proof.

Assume for contradiction that $w(P\setminus\\{p,q\\})<w-r(p)-r(q)$, and let
$T^{\prime}$ be a MST of $P\setminus\\{p,q\\}$. Add $p,q$ to $T^{\prime}$ by
connecting them via edges of length $r(p)$ and $r(q)$, respectively. We obtain
a spanning tree of $G$ whose length is strictly less than

$w(P\setminus\\{p,q\\})+r(p)+r(q)<w-r(p)-r(q)+r(p)+r(q)=w,$

a contradiction. ∎

We can formulate this statement in a slightly more general form that will be
used in the proof of Theorem 5.

######  Lemma 10.

Let $T$ be a minimum spanning tree of a complete geometric graph $G=K_{n}(P)$,
where $w=w(P)$ is the length of $T$. Let
$p_{1}q_{1},p_{2}q_{2},\ldots,p_{k}q_{k}$ be a set of $k$ point pairs on $2k$
distinct points in $P$.

Then $w(P\setminus\\{p_{1},p_{2},\ldots,p_{k}\\})\geq
w-\sum_{i=1}^{k}|p_{i}q_{i}|$.

###### Proof.

Assume for contradiction that
$w(P\setminus\\{p_{1},p_{2},\ldots,p_{k}\\})<w-\sum_{i=1}^{k}|p_{i}q_{i}|$,
and let $T^{\prime}$ be a MST of $P\setminus\\{p_{1},p_{2},\ldots,p_{k}\\}$.
Add $p_{1},p_{2},\ldots,p_{k}$ to $T^{\prime}$ by connecting them via the $k$
edges $p_{1}q_{1},p_{2}q_{2},\ldots,p_{k}q_{k}$, respectively; note that
$q_{1},q_{2},\ldots,q_{k}$ are vertices in $T^{\prime}$. We obtain a spanning
tree of $G$ whose length is strictly less than

$w-\sum_{i=1}^{k}|p_{i}q_{i}|+\sum_{i=1}^{k}|p_{i}q_{i}|=w,$

a contradiction. ∎

##  3 The general case

In this section we prove Theorem 3. Let $p,q\in P$ be the centers of two
disjoint disks whose existence is guaranteed by Lemma 8. Consider the
bipartition of $P$:

$R=P\setminus\\{p,q\\},\ \ B=\\{p,q\\}.$

Let $T$ be a minimum spanning tree of $P$, where $w=w(P)$. By using Lemma 9,
we have

$w(R)\geq w-r(p)-r(q),\text{ and }w(B)=|pq|.$

Consequently, be Lemma 7 we obtain

$\gamma(P)\geq\frac{w(R)+w(B)}{w}\geq\frac{w-r(p)-r(q)+|pq|}{w}>1,$

as required. See Fig. 2

Figure 2: (a) A point set $P$ with a minimum spanning tree, (b) a pair of
disjoint disks in $\mathcal{D}(P)$ defines a bipartition, (c) the minimum
spanning trees of the two parts.

#### Algorithm.

Given $P$, where $|P|=n$, the algorithm only keeps the first (or any) $12$
points of the input for consideration. Denoting this subset by $P^{\prime}$,
the centers of two disjoint balls, say, $p$ and $q$, are found in $P^{\prime}$
in $O(1)$ time. The corresponding partition is $R=P\setminus\\{p,q\\}$, and
$B=\\{p,q\\}$, and the algorithm outputs the smaller set $B$ in $O(1)$ time.
Its correctness follows from Observation 6.

The three relevant spanning trees and the corresponding ratio can be computed
in $O(n\log{n})$ time, see, eg, [4]. This completes the proof of Theorem 3. ∎

Interestingly enough, any sufficiently large point set determines many pairs
of disjoint disks and, therefore, many bipartitions with a ratio $>1$.

######  Proposition 11.

Let $P$ be a set of $n\geq 12$ points in the plane. Then there are at least
$n(n-1)/132$ pairs of disjoint disks in $\mathcal{D}(P)$.

###### Proof.

By Lemma 8, every $12$ points determine at least one pair of disjoint disks in
$\mathcal{D}(P)$. Since each fixed pair appears in exactly ${n-2\choose 10}$
$12$-tuples, $\mathcal{D}(P)$ contains at least

${n\choose 12}\Big{/}{n-2\choose 10}=\frac{n(n-1)}{132}$

pairs of disjoint disks. ∎

By a more careful calculation, the constant $1/132$ in the above statement can
be improved.

##  4 Special cases

###  4.1 Random point sets

#### Proof of Theorem 4.

Let $\beta=\beta(2)$ be the constant from Equation (2). Let
$P=a_{1},a_{2},\ldots,a_{n}$ be a sequence of $n$ random points uniformly
distributed in $[0,1]^{2}$, where $n$ is a large even number. Consider the
bipartition $P=R\cup B$ consisting of the first $n/2$ and the last $n/2$
points, i.e., $R=\\{a_{1},\ldots,a_{n/2}\\}$, and
$B=\\{a_{n/2+1},\ldots,a_{n}\\}$.

By (2),

$w=w(P)\sim\beta\sqrt{n},\ \ w(R)\sim\beta\sqrt{n/2},\text{ and
}w(B)\sim\beta\sqrt{n/2},$

with probability one. Consequently, as $n\to\infty$,

$\gamma(P)\geq\frac{w(R)+w(B)}{w}\geq\frac{2\beta\sqrt{n/2}-o(\sqrt{n})}{\beta\sqrt{n}+o(\sqrt{n})}\geq\sqrt{2}-\varepsilon,$

with probability tending to $1$, as claimed. ∎

###  4.2 Dense point sets

#### Proof of Theorem 5.

Let $P$ be an $n$-element $\alpha$-dense set and $T$ be a minimum spanning
tree of $P$ of length $w$. Since ${\rm diam}(P)\leq\alpha\sqrt{n}$, we may
assume that $P$ is contained in an axis-aligned square $Q$ of side-length
$\alpha\sqrt{n}$. Subdivide $Q$ into $n/4$ axis-parallel squares, called
_cells_ , of side-length $2\alpha$; indeed, $\alpha^{2}n/(4\alpha^{2})=n/4$.
We may assume without loss of generality that no point in $P$ lies on a cell
boundary. We need two preliminary lemmas.

######  Lemma 12.

Each cell contains at most $\frac{2}{\sqrt{3}}(2\alpha+1)^{2}$ points in $P$.

###### Proof.

Let $\sigma\subset Q$ be any cell. Let $\sigma^{\prime}$ be the axis-aligned
square concentric with $\sigma$ and whose side-length is a unit larger than
that of $\sigma$. Its side-length is $2\alpha+1$. Obviously, $\sigma^{\prime}$
contains all open disks of radius $1/2$ centered at the points in
$P\cap\sigma$. Moreover, since $P$ is $\alpha$-dense, these $n$ disks are
disjoint.

Obviously $\sigma^{\prime}$ is a so-called _tiling domain_ , i.e., a domain
that can be used to tile the whole plane [14, Ch. 3.4]. Let $m$ denote the
number of points in $P\cap\sigma$. A standard packing argument requires that
$m\frac{\pi}{4}\leq\frac{\pi}{\sqrt{12}}\,{\rm area}(\sigma^{\prime})$, and
yields $m\leq\frac{2}{\sqrt{3}}(2\alpha+1)^{2}$. ∎

Let $\Sigma$ be the set of $n/4$ cells in $Q$. A cell $\sigma\in\Sigma$ is
said to be _rich_ if it contains at least $2$ points in $P$, and _poor_
otherwise. Let $\mathcal{R}\subset\Sigma$ denote the set of rich cells; and
write $r=|\mathcal{R}|$.

######  Lemma 13.

There are at least $\frac{3\sqrt{3}}{8(2\alpha+1)^{2}}\,n$ rich cells; that
is, $r\geq\frac{3\sqrt{3}}{8(2\alpha+1)^{2}}\,n$.

###### Proof.

Assume for contradiction that $r<\frac{3\sqrt{3}}{8(2\alpha+1)^{2}}\,n$. By
Lemma 12 the total number of points in rich cells is at most

$r\cdot\frac{2}{\sqrt{3}}(2\alpha+1)^{2}<\frac{3\sqrt{3}}{8(2\alpha+1)^{2}}\,n\cdot\frac{2}{\sqrt{3}}(2\alpha+1)^{2}=\frac{3}{4}\,n.$

The total number of points in poor cells is less than
$1\cdot\frac{n}{4}=\frac{n}{4}$. Thus the total number of points in $P$ is
strictly less than $n$, a contradiction that completes the proof. ∎

The following upper bound on $w$ will be needed at the end of the proof.

######  Lemma 14.

We have $w\leq 1.4\alpha n$, for $n$ sufficiently large.

###### Proof.

Few [15] proved that the (Euclidean) length of a shortest cycle (tour) through
$n$ points in the unit square $[0,1]^{2}$ is at most $\sqrt{2n}+7/4$, and the
same upper bound holds for the minimum spanning tree. A slightly better upper
bound $1.392\sqrt{n}+7/4$, is due to Karloff [20]. For large $n$, this is at
most $1.4\sqrt{n}$. Scaling by $\alpha\sqrt{n}$ immediately yields that $w\leq
1.4\alpha n$. ∎

We continue with the proof of the theorem. Decompose $\mathcal{R}$ into $25$
subsets of rich cells as in the decomposition of a $5\times 5$ square into
unit squares. More precisely, consider the tiling of the plane by $5\times 5$
axis-aligned tiles of side-length $2\alpha$. Arbitrarily fix one of the tiles.
A subset corresponds to the rich cells in $Q$ having the same position in the
fixed tile. Each subset satisfies the following properties (recall the side-
length of each cell $2\alpha$):

  1. i

the distance between any two points in the same cell is at most
$2\sqrt{2}\alpha$.

  2. ii

the distance between any two points in different cells is at least $8\alpha$.

By averaging, one of the subsets, $\mathcal{R}^{\prime}$, contains
$k\geq\lceil|\mathcal{R}|/25\rceil$ rich cells. Note that

$k\geq\frac{3\sqrt{3}}{200(2\alpha+1)^{2}}\,n,$ (3)

by Lemma 13. Arbitrarily choose two points $p_{i},q_{i}$ in each of the $k$
rich cells. Now consider the bipartition of $P$:

$R=P\setminus\\{p_{1},p_{2},\ldots,p_{k}\\},\ \
B=\\{p_{1},p_{2},\ldots,p_{k}\\}.$

By Lemma 10 and the first property of $\mathcal{R}^{\prime}$ we have

$w(R)\geq w-\sum_{i=1}^{k}|p_{i}q_{i}|\geq w-2\sqrt{2}\alpha k.$

On the other hand, by the second property of $\mathcal{R}^{\prime}$ we have

$w(B)\geq 8\alpha(k-1).$

Consequently, by Lemma 14 and the fact that $n$ (thus also $k$ according to
(3)) is sufficiently large, we obtain

$\displaystyle\gamma(P)$
$\displaystyle\geq\frac{w(R)+w(B)}{w}\geq\frac{w+2(4-\sqrt{2})\alpha
k-8\alpha}{w}\geq\frac{w+5\alpha k}{w}$ $\displaystyle\geq 1+\frac{5\alpha
k}{1.4\alpha n}=1+\frac{3\sqrt{3}}{56(2\alpha+1)^{2}}\geq
1+\frac{1}{11(2\alpha+1)^{2}}$ $\displaystyle=1+\Omega(\alpha^{-2}),$

as required. This completes the proof of Theorem 5. ∎

It is likely that using a hexagonal tiling gives a slightly better constant in
the bound, however, the dependence of the bound on $\alpha$ remains quadratic.

##  5 Concluding remarks

The techniques used to handle the planar case immediately extend to
$\mathbb{R}^{d}$ for any fixed dimension $d$. Specifically we need the
_disjoint balls_ property; we rely on estimates due to Füredi and Loeb [16],
given in (4). Let $\kappa(d)$ denote the maximum number of balls in
$\mathbb{R}^{d}$ that can form a configuration where each ball intersects
every other ball but does not contain the center of any other ball. As
mentioned earlier, it is known that $8\leq\kappa(2)\leq 11$. The following
bounds hold in $d$-space:

$1.25^{d}\leq\kappa(d)\leq(1.887\ldots+o(1))^{d}.$ (4)

The proof of Theorem 15 is analogous to that of Theorem 3 and is therefore
omitted.

######  Theorem 15.

For every fixed $d$, there exists $n_{d}\in\mathbb{N}$ with the following
property. For any set $P$ of $n\geq n_{d}$ points in $\mathbb{R}^{d}$ we have
$\gamma(P)>1$. A suitable bipartition with this ratio can be computed in
$O(1)$ time.

We have seen that the disjoint balls property implies that the maximum MST
ratio is strictly larger than $1$. However, the two properties are not
equivalent.

Another related question is how the $\gamma$ ratio changes when points are
added to a set. Suppose that $P_{0}$ is a point set with $\gamma(P_{0})>1$,
and an infinite sequence of points, $p_{1},p_{2},\ldots$, are successively
added to $P_{0}$. By Theorem 3, $\gamma(P_{0}\cup\\{p_{1},\ldots,p_{n}\\})>1$
for every $n$ such that $|P_{0}|+n\geq 12$. Is it possible that
$\gamma(P_{0}\cup\\{p_{1},\ldots,p_{n}\\})$ tends to $1$ as $n\to\infty$? We
give a positive answer. Assuming that the first $n$ points
$p_{1},\ldots,p_{n}$ are known, let $P_{n}=P_{0}\cup\\{p_{1},\ldots,p_{n}\\}$,
$w_{n}=w(P_{n})$, and $D_{n}={\rm diam}(P_{n})$, where $a_{n},b_{n}$ is a
diameter pair in $P_{n}$. Assume that $\gamma(P_{n})\leq 1+\varepsilon$ for
some $\varepsilon>0$, we can select $p_{n+1}$ so that $\gamma(P_{n+1})\leq
1+\varepsilon/2$, for every $n$. Let $p_{n+1}$ be a point on the line incident
to $a_{n},b_{n}$ at a sufficiently large distance $f(w_{n},\varepsilon)$ from
$b$, with $a_{n},b_{n},p_{n+1}$ appearing in this order. The verification that
the above inequality holds, for a suitable function $f$, is left to the
reader. Observe that the above construction is analogous to the upper bound
construction in Proposition 2; and works in any dimension.

We conclude with three open problems:

  1. 1.

We have seen that $\gamma(P)>1$ can be arbitrarily close to $1$ even for large
$n$, whereas it is separated from $1$ by a positive gap for randomly uniformly
distributed sets and for $\alpha$-dense sets. In what other cases can one
deduce $\gamma(P)>1+\lambda$ for a positive constant $\lambda$?

  2. 2.

Is there an efficient algorithm for computing the maximum ratio, $\gamma(P)$?

  3. 3.

Is the $\sqrt{2}$ lower bound for randomly uniformly distributed sets in the
unit square tight?

Acknowledgement. We are grateful to Herbert Edelsbrunner for calling our
attention to the subject and for his valuable remarks. In particular, he
communicated to us the construction in the second half of Proposition 2.

## References

  * [1] Tetsuo Asano, Binay Bhattacharya, Mark Keil, and Frances Yao, Clustering algorithms based on minimum and maximum spanning trees, _Proc. $4$th Annual Symposium on Computational Geometry_, 1988, pp. 252–257.
  * [2] Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor, On metric Ramsey-type phenomena, _Ann. Math._ 162(2) (2005), 643–709.
  * [3] Jillian Beardwood, John H. Halton, and John M. Hammersley, The shortest path through many points, _Mathematical Proceedings of the Cambridge Philosophical Society_ 55(4) (1959), 299–327.
  * [4] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, _Computational Geometry_ , 3rd edition, Springer, Heidelberg, 2008.
  * [5] Dimitris J. Bertsimas and Garrett Van Ryzin, An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability, _Operations Research Letters_ 9(4) (1990), 223–231.
  * [6] Peter Braß, William Moser, and János Pach, _Research Problems in Discrete Geometry_ , Springer, New York, 2005.
  * [7] Fan R. K. Chung and Ronald L. Graham, A new bound for Euclidean Steiner minimal trees, _Annals of the New York Academy of Sciences_ 440(1), (1985), 328–346.
  * [8] Fan R. K. Chung, On the decomposition of graphs, _SIAM Journal on Algebraic Discrete Methods_ 2(1), (1981), 1–12.
  * [9] Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. Persistent homology of chromatic alpha complexes, _arXiv:2212.03128_.
  * [10] Sebastiano Cultrera di Montesano, Ondřej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. Measuring the mingling of colored points, communication at the _Convex and Discrete Geometry Workshop_ , Sept. 4–8, 2023, Alfréd Rényi Institute of Mathematics, Budapest, Hungary.
  * [11] Ding -Z. Du and Frank K. Hwang, A new bound for the Steiner ratio, _Transactions of the American Mathematical Society_ 278(1), (1983), 137–148.
  * [12] Paul Erdős and András Hajnal, On decomposition of graphs, _Acta Math. Acad. Sci. Hungar_ 18 (1967), 359–377.
  * [13] László Fejes Tóth, Über einen geometrischen Satz, _Mathematische Zeitschrift_ 46(1) (1940), 83–85.
  * [14] László Fejes Tóth, Gábor Fejes Tóth, and Włodzimierz Kuperberg, _Lagerungen_ , Springer Nature Switzerland, 2023.
  * [15] Leonard Few, The shortest path and shortest road through $n$ points, _Mathematika_ 2 (1955), 141–144.
  * [16] Zoltán Füredi and Peter A. Loeb, On the best constant for the Besicovitch covering theorem, _Proceedings of the American Mathematical Society_ 121(4) (1994), 1063–1073.
  * [17] Edgar N. Gilbert and Henry O. Pollak, Steiner minimal trees, _SIAM Journal on Applied Mathematics_ 16(1) (1968), 1–29.
  * [18] Ronald L. Graham and Frank K. Hwang, Remarks on Steiner minimal trees, _Bull. Inst. Math. Acad. Sinica_ 4(1) (1976), 177–182.
  * [19] Frank Harary, Michael S. Jacobson, Marc J. Lipman, and Fred R. McMorris, Abstract sphere-of-influence graphs, _Mathematical and Computer Modelling_ , 17(11) (1993), 77–83.
  * [20] Howard J. Karloff, How long can a Euclidean traveling salesman tour be? _SIAM Journal of Discrete Mathematics_ 2 (1989), 91–99.
  * [21] A. E. Kézdy and G. Kubicki, $K_{12}$ is not a closed sphere-of-influence graph, _Intuitive Geometry_ János Bolyai Mathematical Society, Budapest, 6 (1997), 383–397.
  * [22] László Lovász, On decompositions of graphs, _Studia Scientiarum Mathematicarum Hungarica_ 1 (1966), 237–-238.
  * [23] Michael J. Steele, _Probability Theory and Combinatorial Optimization_ , SIAM, Philadelphia, 1997.
  * [24] Pavel Valtr, Convex independent sets and 7-holes in restricted planar point sets, _Discrete & Computational Geometry_ 7(2) (1992), 135–152.
  * [25] Pavel Valtr, _Planar point sets with bounded ratios of distances_ , PhD Thesis, Freie Universität Berlin (1994).
  * [26] Samuel Verblunsky, On the shortest path through a number of points, _Proceedings of the American Mathematical Society_ 2(6) (1951), 904–913.