# On a Traveling Salesman Problem for Points in the Unit Cube

József Balogh111Department of Mathematics, University of Illinois at Urbana-
Champaign, Urbana, Illinois 61801, USA, E-mail<EMAIL_ADDRESS>Research
is partially supported by NSF grant DMS-1764123. Felix Christian
Clemen222Department of Mathematics, Karlsruhe Institute of Technology, 76131
Karlsruhe, Germany, E-mail<EMAIL_ADDRESS>Adrian
Dumitrescu333Algoresearch L.L.C., Milwaukee, WI 53217, USA, E-mail:
<EMAIL_ADDRESS>
###### Abstract

Let $X$ be an $n$-element point set in the $k$-dimensional unit cube
$[0,1]^{k}$ where $k\geq 2$. According to an old result of Bollobás and Meir
(1992), there exists a cycle (tour) $x_{1},x_{2},\ldots,x_{n}$ through the $n$
points, such that $\left(\sum_{i=1}^{n}|x_{i}-x_{i+1}|^{k}\right)^{1/k}\leq
c_{k}$, where $|x-y|$ is the Euclidean distance between $x$ and $y$, and
$c_{k}$ is an absolute constant that depends only on $k$, where $x_{n+1}\equiv
x_{1}$. From the other direction, for every $k\geq 2$ and $n\geq 2$, there
exist $n$ points in $[0,1]^{k}$, such that their shortest tour satisfies
$\left(\sum_{i=1}^{n}|x_{i}-x_{i+1}|^{k}\right)^{1/k}=2^{1/k}\cdot\sqrt{k}$.
For the plane, the best constant is $c_{2}=2$ and this is the only exact value
known. Bollobás and Meir showed that one can take
$c_{k}=9\left(\frac{2}{3}\right)^{1/k}\cdot\sqrt{k}$ for every $k\geq 3$ and
conjectured that the best constant is $c_{k}=2^{1/k}\cdot\sqrt{k}$, for every
$k\geq 2$. Here we significantly improve the upper bound and show that one can
take $c_{k}=3\sqrt{5}\left(\frac{2}{3}\right)^{1/k}\cdot\sqrt{k}$ or
$c_{k}=2.91\sqrt{k}\ (1+o_{k}(1))$. Our bounds are constructive. We also show
that $c_{3}\geq 2^{7/6}$, which disproves the conjecture for $k=3$.

Connections to matching problems, power assignment problems, related problems,
including algorithms, are discussed in this context. A slightly revised
version of the Bollobás–Meir conjecture is proposed.

Keywords: traveling salesman problem, minimum spanning tree, binary code,
relaxed triangle inequality.

##  1 Introduction

Given $n$ points in the unit square, Newman [20, Problem 57] proved that there
is a closed polygonal Hamiltonian cycle (tour) $H$ through the $n$ points such
that the sum of the squares of its edge-lengths is at most $4$. The upper
bound of $4$ cannot be improved: Figure 1 shows three different point sets
whose optimal tours yield exact equality. More importantly, the above upper
bound is independent of $n$.

Figure 1: Tight examples with $4,2$, and $5$ points:
$1+1+1+1=2+2=1+1+1+1/2+1/2$.

Meir [19] considered the extension of this problem to higher dimensions. For a
point $x\in\mathbb{R}^{k}$, let $|x|$ denote the Euclidean length of $x$;
namely, if $x=(\xi_{1},\xi_{2},\ldots,\xi_{k})$, then
$|x|=\left(\sum_{i=1}^{k}\xi_{i}^{2}\right)^{1/2}$. For two points
$x,y\in\mathbb{R}^{k}$, let the _weight_ of the edge $e=xy$, be $|e|:=|x-y|$,
i.e., the Euclidean distance between $x$ and $y$.

Let $X$ be an $n$-element point set in the unit cube $[0,1]^{k}$. For a graph
$G$ on vertex set $X$, set

$\displaystyle S_{k}(G)$ $\displaystyle=\sum_{e\in G}|e|^{k}\quad\text{ and
}\quad s_{k}(G)=\left(\sum_{e\in G}|e|^{k}\right)^{1/k}.$ (1)

We refer to $S_{k}(G)$ and $s_{k}(G)$ as the _unscaled_ and _scaled_ costs,
respectively. Denote by $S_{k}^{\texttt{HC}}(X)$, $S_{k}^{\texttt{ST}}(X)$ and
$S_{k}^{\texttt{HP}}(X)$ ($s_{k}^{\texttt{HC}}(X)$, $s_{k}^{\texttt{ST}}(X)$
and $s_{k}^{\texttt{HP}}(X)$) the minimum over $S_{k}(G)$ ($s_{k}(G)$) where
$G$ is a Hamiltonian cycle, respectively a spanning tree or Hamiltonian Path
with vertex set $X$. Further, let

$\displaystyle s_{k}^{\texttt{HC}}(n)=\sup\\{s_{k}^{\texttt{HC}}(X)\colon
X\subseteq[0,1]^{k},|X|=n\\},\quad
s_{k}^{\texttt{ST}}(n)=\sup\\{s_{k}^{\texttt{ST}}(X)\colon
X\subseteq[0,1]^{k},|X|=n\\},$ $\displaystyle
s_{k}^{\texttt{HP}}(n)=\sup\\{s_{k}^{\texttt{HP}}(X)\colon
X\subseteq[0,1]^{k},|X|=n\\},$ $\displaystyle s_{k}^{\texttt{HC}}=\sup_{n\geq
2}s_{k}^{\texttt{HC}}(n),\quad s_{k}^{\texttt{ST}}=\sup_{n\geq
2}s_{k}^{\texttt{ST}}(n)\quad\text{and}\quad s_{k}^{\texttt{HP}}=\sup_{n\geq
2}s_{k}^{\texttt{HP}}(n).$

It is clear that $s_{k}^{\texttt{HC}}(n)\geq s_{k}^{\texttt{HC}}(m)$, whenever
$n\geq m$ (by clustering points and taking the limit). In this notation,
Newman’s result mentioned earlier reads $s_{2}^{\texttt{HC}}(n)=2$ for every
$n\geq 2$. A more recent reference to this result can be found in [6, Problem
124]. Currently this is the only exact value known. Meir [19] asked whether
$s_{k}(n)$ is bounded from above by a constant $c_{k}>0$ for every $k$. Soon
after, Bollobás and Meir [7] answered Meir’s question in the positive by
proving that $s_{k}^{\texttt{HC}}(n)\leq
9\left(\frac{2}{3}\right)^{1/k}\cdot\sqrt{k}$ for every $k\geq 3$ and $n\geq
2$ (and recall that $c_{2}=2$). From the other direction, the $2$-point
example consisting of two opposite vertices of $\\{0,1\\}^{k}$ shows that
$s_{k}^{\texttt{HC}}(n)\geq 2^{1/k}\cdot\sqrt{k}$ for every $k\geq 2$ and
$n\geq 2$; see Figure 1 (center). We record their result below.

######  Theorem 1.1.

(Bollobás and Meir [7]). Let $k\geq 3$ and $n\geq 2$. Then,

$2^{1/k}\sqrt{k}\leq s_{k}^{\texttt{HC}}(n)\leq
3^{2-\frac{1}{k}}2^{1/k}\sqrt{k}.$

In the conclusion of their paper [7], the authors conjectured that
$s_{k}^{\texttt{HC}}(n)=2^{1/k}\cdot\sqrt{k}$ for every $k\geq 2$ and $n\geq
2$. Meir [19] also asked for an algorithm that computes a tour whose cost is
bounded by a constant depending on $k$. As we will see in more detail in
Section 2, Bollobás and Meir’s proof implicitly gives a positive answer to
this latter question. Similarly, our new bounds in Theorem 1.3 and Corollary
5.1 are constructive too.

#### Background and related work.

The _traveling salesman problem_ (TSP) is perhaps the most studied problem in
the theory of combinatorial optimization. Its approximability depends on the
particular version of the problem. Specifically, TSP with Euclidean distances
admits a polynomial-time approximation scheme [3, 16]. If the distances form a
metric, then the problem is $\MaxSNP$-hard [21] and the best approximation
ratio known is essentially $3/2$ [8, 13].

Estimating the length of a shortest 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 [10], Few [11], and Verblunsky [30], respectively. Few [11] 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$. The same upper bound
holds for the minimum spanning tree [11]. Few’s bound was rediscovered in 1983
by Supowit, Reingold, and Plaisted [26]. A slightly better upper bound for the
shortest cycle, $1.392\sqrt{n}+7/4$, has been derived by Karloff [14], who
also emphasized the difficulty of the problem. The current best lower bound
for the length of such a cycle is due to Fejes Tóth [10] and Few [11]: it is
$\left(\frac{4}{3}\right)^{1/4}\sqrt{n}-o(\sqrt{n})$, where
$(4/3)^{1/4}=1.075\ldots$. For every dimension $k\geq 3$, Few showed that the
maximum length of a shortest tour through $n$ points in the unit cube is
$\Theta(n^{1-1/k})$. Moran [18] studied the length of the shortest traveling
salesman tour through a set of $n$ points of unit diameter in
$\mathbb{R}^{k}$.

The length of a shortest tour through a random sample
$\\{X_{1},\ldots,X_{n}\\}$ of $n$ points in the unit cube $[0,1]^{k}$ was
determined by Beardwood, Halton, and Hammersley. Let this length be denoted by
$L(X_{1},\ldots,X_{n})$. If $\\{X_{i}\\}$ is a sequence of independent random
variables with the uniform distribution on $[0,1]^{k}$, then there is a
constant $\beta(k)>0$ such that

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

with probability one [4]. Later, Rhee [22] proved that
${\beta(k)/\sqrt{k}}\to{1/\sqrt{2\pi e}}$, see also [25]. The relevance of the
cube diagonal, $\sqrt{k}$, in the above formulas, can be also observed in our
estimates for $s_{k}(n)$; see Theorem 1.3 (ii) and Conjecture 5.5.

Expressions for the cost of a Hamiltonian cycle of the kind in (1) have been
considered in the context of _power assignment_ problems in wireless networks.
Let $X$ be an $n$-element point set in the unit cube $[0,1]^{k}$ and
$\alpha\geq 1$ be a real number. For a Hamiltonian cycle $H$ as above, one is
interested in minimizing a cost of the form

${\rm cost}(H)=\sum_{i=1}^{n}|x_{i}-x_{i+1}|^{\alpha}.$ (2)

Such costs typically reflect the _energy_ costs along the edges that make the
cycle [9, 15] in wireless network transmission. An illustrative example is
that of a _virtual token_ floating through the network, where sensor nodes can
attach or read data from the token before sending it to the next node on the
cycle. One can speak about finding a traveling salesman tour (TSP tour) of
minimum energy cost [12]. The fact that $k$ is the smallest value of $\alpha$
for which the cost in (2) is bounded from above by a constant (depending on
$k$ but independent on $n$) should be noted [7, 15]; a fine grid section in
the cube proves this point.

As pointed out in several places in the literature [2, 5, 9, 12], simply
computing a short (even optimal) tour for the underlying Euclidean instance
does not work, i.e., does not provide a good approximation with respect to the
power costs in (2). Funke, Laue, Lotker and Naujoks [12] showed that the cost
of an optimal tour for the Euclidean instance can be a factor of $\Omega(n)$
larger than that of optimal tour for the power costs (a simple example can be
constructed with equidistant points on a line or on a circle of large radius).

In [12] a recursive algorithm was also presented, that given $n$ points in
$\mathbb{R}^{2}$ constructs a TSP tour for edge costs
$|pq|^{\alpha}=|e|^{\alpha}$, whose cost is at most $2\cdot 3^{\alpha-1}$
times that of a minimum spanning tree (MST) of the point set. Since the cost
of an MST does not exceed that of an optimal Euclidean TSP tour, their
algorithm is $2\cdot 3^{\alpha-1}$-factor approximation for the TSP with power
costs as in (2). The authors further show that the approach extends to
$\mathbb{R}^{k}$ with the same ratio:

######  Theorem 1.2.

(Funke, Laue, Lotker, and Naujoks [12]). There exists a $2\cdot
3^{\alpha-1}$-approximation algorithm for the TSP in $\mathbb{R}^{k}$ if the
edge weights are Euclidean distances to the power $\alpha$.

If for some $\tau>1$ distances of a TSP instance satisfy

${\rm dist}(x,z)\leq\tau\left({\rm dist}(x,y)+{\rm dist}(y,z)\right),$

for any three vertices $x,y,z$, we say that they satisfy the _relaxed triangle
inequality_ , see [2, 5, 17]. It is important to note that the metric with
Euclidean distances to the power $\alpha$ satisfies the relaxed triangle
inequality with $\tau=2^{\alpha-1}$; see [9, 12]. For $\alpha=2$ (i.e., TSP
with squared distances), Theorem 1.2 yields a $6$-approximation. De Berg, van
Nijnatten, Sitters, Woeginger and Wolff [9] obtained a $5$-approximation.

#### Our results.

The upper bound $s_{k}^{\texttt{HC}}(n)\leq
9\left(\frac{2}{3}\right)^{1/k}\cdot\sqrt{k}$, where $k\geq 3$, has stood
unchanged for $30$ years [7]. Here we obtain several improvements.

######  Theorem 1.3.

The following bounds are in effect:

  * (i)

There exists a $4$-element point set in $[0,1]^{3}$ such that the cost of the
shortest tour is at least $2^{7/6}=2.24\ldots$. Consequently,
$s_{3}^{\texttt{HC}}(n)\geq 2^{7/6}=2.24\ldots$, for every $n\geq 4$.

  * (ii)

Let $X$ be an $n$-element point set in the $k$-dimensional unit cube
$[0,1]^{k}$, $k\geq 3$. Then there exists a tour $H=x_{1},x_{2},\ldots,x_{n}$
through the $n$ points, such that
$\left(\sum_{i=1}^{n}|x_{i}-x_{i+1}|^{k}\right)^{1/k}\leq
3\sqrt{5}\left(\frac{2}{3}\right)^{1/k}\cdot\sqrt{k}$. Consequently,
$s_{k}^{\texttt{HC}}(n)\leq
3\sqrt{5}\left(\frac{2}{3}\right)^{1/k}\cdot\sqrt{k}=6.708\ldots\cdot\left(\frac{2}{3}\right)^{1/k}\cdot\sqrt{k}$.

  * (iii)

$H$ can be computed in time proportional to that needed for computing a MST of
the points, in particular, in subquadratic time.

Several sharper bounds are obtained for sufficiently large $k$. We note that
the conjectured optimal configuration consisting of a diameter pair of the
cube as well as the lower bound construction we will present for $k=3$ in
Theorem 1.3 (i) are subsets of $\\{0,1\\}^{k}$. This raises the natural
question if one can determine the maximum of $s_{k}^{\texttt{HC}}(X)$ if the
point set $X$ is in $\\{0,1\\}^{k}$. We answer this question.

######  Theorem 1.4.

There exists an integer $k_{0}$ such that for all $k\geq k_{0}$ the following
holds. If $X$ is an arbitrary subset of vertices of $\\{0,1\\}^{k}$, then
there exists a Hamiltonian cycle $H$ through $X$ such that $s_{k}(H)\leq
2^{1/k}\sqrt{k}$. This bound is best possible.

The “sufficiently large” requirement for Theorem 1.4 is in fact quite modest.
The threshold $k_{0}$ is below $30$.

######  Theorem 1.5.

For the family of minimum spanning trees, we have

$s_{k}^{\texttt{ST}}\leq\sqrt{k}\ (1+o_{k}(1)).$

Apart from the error term, this bound is best possible.

By transforming a minimum spanning tree into a Hamiltonian cycle by using the
method of Sekanina [23] and Bollobás and Meir [7], we obtain
$s_{k}^{\texttt{HC}}\leq 3\sqrt{k}\ (1+o_{k}(1))$. A further refinement based
on a two-phase algorithm and a new greedy algorithm that maintains a
collection of spanning paths allows us to obtain the following sharper bound.

######  Theorem 1.6.

For the family of Hamiltonian cycles, we have

$s_{k}^{\texttt{HC}}\leq 2.91\sqrt{k}\ (1+o_{k}(1)).$

When the number of points $n$ is bounded by a constant (independent of $k$),
we can obtain a better asymptotic bound, close to the conjectured value
$2^{1/k}\sqrt{k}$.

######  Theorem 1.7.

Let $n\geq 2$ be fixed. For the family of Hamiltonian cycles, we have

$s_{k}^{\texttt{HC}}(n)=2^{1/k}\sqrt{k}\ (1+o_{k}(1)).$

Note however, that in Theorem 1.7 we require $n$ to be constant; it does not
imply $s_{k}^{\texttt{HC}}=2^{1/k}\sqrt{k}\ (1+o_{k}(1))$.

The improved upper bounds in Theorem 1.3 and 1.6, have implications for the
existence of Hamiltonian paths and perfect matchings whose costs are bounded
from above by constants depending on $k$. These are discussed in Section 5.

##  2 Hamiltonian cycles: exact upper and lower bounds

###  2.1 An improved lower bound for $k=3$

In this subsection we prove Theorem 1.3(i). Consider the four-element point
set

$X=\\{(0,0,0),(0,1,1),(1,0,1),(1,1,0)\\}\subset[0,1]^{3}.$

$X$ is in fact a _binary code_ of length $3$ with _minimum Hamming distance_
$2$; see, e.g., [29, Ch. 5]. As such, the corresponding Euclidean pairwise
distances are at least $\sqrt{2}$. Consequently, the unscaled cost of any TSP
tour $H$ is at least $S_{k}(H)\geq 4\cdot(\sqrt{2})^{3}=11.31\ldots$. On the
other hand, the conjectured [7] optimal unscaled cost was
$2\cdot(\sqrt{3})^{3}=10.39\ldots$. ∎

It is possible that the new lower bound gives the right value of
$s_{3}^{\texttt{HC}}(n)$ for $n\geq 4$, see Conjecture 5.5 in Section 5.

#### Remark.

Interestingly enough, for $k=4$, there exist (at least) two different point
sets, one with $n=2$ and the other with $n=8$, whose shortest tours have the
same cost $S_{4}^{\texttt{HC}}(X)$ as the conjectured value,
$S_{4}^{\texttt{HC}}(n)=2\cdot(\sqrt{4})^{4}=32$. The former set consists of a
pair of diagonally opposite vertices, say, $\\{(0,0,0,0),(1,1,1,1)\\}$. This
is in fact the point set that is behind the conjectured maximum cost for
_every_ $k$. The latter set is a binary code of length $4$ with minimum
distance $2$; for example, one can take the eight binary vectors with an even
number of ones:

$\displaystyle
X=\\{(0,0,0,0),(0,0,1,1),(0,1,0,1),(0,1,1,0),(1,0,0,1),(1,0,1,0),(1,1,0,0),(1,1,1,1)\\}.$

Then $S_{4}^{\texttt{HC}}(X)\geq 8(\sqrt{2})^{4}=32$ and this value can be
attained; equivalently, $s_{4}^{\texttt{HC}}(X)\geq 2^{5/4}$. We were not able
to find two different sets $X$ with $s_{k}^{\texttt{HC}}(X)\geq
2^{1/k}\cdot\sqrt{k}$ for any other $k\geq 5$.

###  2.2 An improved upper bound for every $k\geq 3$

In this section we prove the last two items in Theorem 1.3. Our proof is
modeled by that in [7]. It uses a ball packing argument based on the following
lemma. (A similar lemma, however, with smaller ball radii, can be found in
[15].)

######  Lemma 2.1.

(Bollobás and Meir [7]). Let $T=(V,E)$ be a minimum spanning tree for a finite
point set $X\subset\mathbb{R}^{k}$. For each edge $e=xy\in E$ let $B_{e}$ be
the open ball of radius $\frac{1}{4}|x-y|$ centered at $\frac{1}{2}(x+y)$.
Then $B_{e}\cap B_{e^{\prime}}=\emptyset$ whenever $e$ and $e^{\prime}$ are
edges of $T$. The factor $\frac{1}{4}$ is as large as possible.

In addition, a suitable order of traversing the vertices of a minimum spanning
tree first developed by Sekanina [23, 24] is needed. The algorithm can be made
to run in linear time. A proof of this traversal result — in slightly
different terms — also appears in [7]. A few definitions and notations (from
[7]) are as follows. The _$h$ ’th power_ $G^{h}$ of a graph $G=(V,E)$ is the
graph with vertex set $V$ and edge set $E(G^{h})=\\{xy\colon x,y\in V,1\leq
d(x,y)\leq h\\}$. Here $d(x,y)$ is the distance between $x$ and $y$ in the
graph. Let $T$ be a tree and $xy\in E(T^{h})$. An edge $uv\in E(T)$ is said to
be _used by_ $xy$ if the edge $uv$ is on the unique path in $T$ (of length at
most $h$) from $x$ to $y$. If $H$ is a subgraph of $T^{h}$, then an edge of
$T$ is _used $t$ times by_ $H$ if it is used by $t$ edges of $H$.

######  Lemma 2.2.

(Sekanina [23], Bollobás and Meir [7]). Let $x$ be a vertex of a tree $T$ with
at least $3$ vertices. Then $T^{3}$, the cube of $T$, contains a Hamiltonian
cycle $H$ such that every edge of $T$ is used exactly twice by $H$, and one of
the edges of $H$ incident to $x$ is an edge of $T$.

It implies the following lemma which is not stated explicitly in [7] but is
used in the proof of their Theorem 3. For completeness, we include their proof
here.

######  Lemma 2.3.

(Bollobás and Meir [7]). Let $T$ be a spanning tree for a finite point set
$X\subset\mathbb{R}^{k}$. Then there exists a Hamiltonian cycle $H$ on $X$
such that

$\displaystyle S_{k}(H)\leq\frac{2}{3}\cdot 3^{k}\cdot S_{k}(T).$

###### Proof.

Let $e_{1},\ldots,e_{n}$ be the edges of a Hamiltonian cycle $H$ in $T^{3}$
guaranteed by Lemma 2.2. Suppose that the edges of $T$ used by $e_{i}$ have
lengths $d_{i_{1}},\ldots,d_{i_{\ell}}$, where $\ell\leq 3$. Set
$f_{i}=d_{i_{1}}+\ldots+d_{i_{\ell}}$ and
$f=(f_{i})_{i\in[n]}\in\mathbb{R}^{n}$. Then $|e_{i}|\leq f_{i}$ for every
$i$, each $f_{i}$ is a sum of at most three $d_{j}$’s and each $d_{j}$ occurs
in the representations of two $f_{i}$’s.

Now, we can form three vectors $v_{1},v_{2},v_{3}\in\mathbb{R}^{n}$ such that
$f=v_{1}+v_{2}+v_{3}$, every coordinate of $v_{i}$ is a $d_{j}$ or 0, and
every $d_{j}$ occurs exactly twice as a coordinate in the three $v_{i}$’s.
Therefore, $\sum_{i=1}^{3}\lVert
v_{i}\rVert_{k}^{k}=2\sum_{j=1}^{n-1}d_{j}^{k}$. Hence, by the triangle-
inequality and Jensen’s inequality,

$\displaystyle\lVert f\rVert_{k}$ $\displaystyle=\lVert
v_{1}+v_{2}+v_{3}\rVert_{k}\leq\sum_{i=1}^{3}\lVert v_{i}\rVert_{k}\leq
3\left(\frac{1}{3}\sum_{i=1}^{3}\lVert v_{i}\rVert_{k}^{k}\right)^{1/k}$
$\displaystyle=3\left(\frac{2}{3}\sum_{j=1}^{n-1}d_{j}^{k}\right)^{1/k}=3\left(\frac{2}{3}\right)^{1/k}\cdot
s_{k}(T),$

and thus

$S_{k}(H)=\sum_{i=1}^{n}|e_{i}|^{k}\leq\lVert
f\rVert_{k}^{k}\leq\frac{2}{3}\cdot 3^{k}\cdot S_{k}(T).\qed$

For convenience, here we work with the unit cube $U=[-1/2,1/2]^{k}$ centered
at the origin $o=(0,\ldots,0)$. Assume that $n\geq 3$, since it is clear
otherwise that $s_{k}(H)\leq 2^{1/k}\cdot\sqrt{k}$. It was shown in [7] that
$\cup_{e\in T}B_{e}$ is contained in the ball of radius $0.75\sqrt{k}$
centered at the origin $o$. We next show that $\cup_{e\in T}B_{e}$ is
contained in the ball of radius
$\frac{\sqrt{5}}{4}\sqrt{k}=0.559\ldots\cdot\sqrt{k}$ centered at $o$. The
idea for the improvement is that centers of balls corresponding to long edges
of $T$ cannot be too far from the center of the cube. The key step is the
following.

######  Lemma 2.4.

Let $U=[-1/2,1/2]^{k}$ and $u,v\in U$. Then

$\frac{|u+v|}{2}+\frac{|u-v|}{4}\leq\frac{\sqrt{5}}{4}\sqrt{k}.$ (3)

This inequality is the best possible.

###### Proof.

To start with, note that

$\displaystyle|u|^{2}\leq\sum_{1}^{k}\frac{1}{4}=\frac{k}{4},\quad\quad|v|^{2}\leq\sum_{1}^{k}\frac{1}{4}=\frac{k}{4}\quad\quad\text{and}\quad\quad|u-v|\leq\sqrt{k}.$

The first two relations immediately yield

$|u|^{2}+|v|^{2}\leq\frac{k}{2}.$ (4)

Recall the identities

$\displaystyle|u+v|^{2}=|u|^{2}+|v|^{2}+2uv,\quad\quad|u-v|^{2}$
$\displaystyle=|u|^{2}+|v|^{2}-2uv.$ (5)

Here $uv$ is the dot product of $u$ and $v$. We deduce that

$|u-v|^{2}=2(|u|^{2}+|v|^{2})-|u+v|^{2}\leq 2(|u|^{2}+|v|^{2}).$

We can thus write $|u-v|=\lambda\sqrt{|u|^{2}+|v|^{2}}$, where
$0\leq\lambda\leq\sqrt{2}$, whence

$|u-v|^{2}=\lambda^{2}(|u|^{2}+|v|^{2}).$

From the two equations in (5) we also obtain

$\displaystyle|u+v|=\sqrt{2(|u|^{2}+|v|^{2})-|u-v|^{2}}=\sqrt{(2-\lambda^{2})(|u|^{2}+|v|^{2})}.$

Substituting the expressions of $|u+v|$ and $|u-v|$ and using (4) yields

$\displaystyle\frac{|u+v|}{2}+\frac{|u-v|}{4}$
$\displaystyle=\frac{\sqrt{(2-\lambda^{2})(|u|^{2}+|v|^{2})}}{2}+\frac{\lambda\sqrt{|u|^{2}+|v|^{2}}}{4}=\left(\frac{\sqrt{2-\lambda^{2}}}{2}+\frac{\lambda}{4}\right)\sqrt{|u|^{2}+|v|^{2}}$
$\displaystyle\leq\frac{1}{4}\left(\lambda+2\sqrt{2-\lambda^{2}}\right)\sqrt{\frac{k}{2}}.$

A standard calculation shows that the function
$f(\lambda)=\lambda+2\sqrt{2-\lambda^{2}}$, where $0\leq\lambda\leq\sqrt{2}$,
attains its maximum, $\sqrt{10}$, at $\lambda=\sqrt{\frac{2}{5}}$.
Consequently,

$\displaystyle\frac{|u+v|}{2}+\frac{|u-v|}{4}$
$\displaystyle\leq\frac{1}{4}\sqrt{10}\sqrt{\frac{k}{2}}=\frac{\sqrt{5}}{4}\sqrt{k}.$

This concludes the proof of the upper bound.

For a tight example, assume that $k$ is a multiple of $5$ and let
$u=u_{1},\ldots,u_{k}$, and $v=v_{1},\ldots,v_{k}$, where

$\displaystyle u_{i}$
$\displaystyle=\left\\{\begin{array}[]{ll}+\frac{1}{2},&\text{ for
}i=1,\ldots,\frac{4k}{5},\\\ -\frac{1}{2},&\text{ for
}i=\frac{4k}{5}+1,\ldots,k.\end{array}\right.$ $\displaystyle v_{i}$
$\displaystyle=+\frac{1}{2},\ \ \ \ \text{ for }i=1,\ldots,k.$

It is now easily verified that

$\displaystyle\frac{|u+v|}{2}=\sqrt{\frac{4k}{5}\cdot\frac{1}{4}},\quad\quad\frac{|u-v|}{4}=\sqrt{\frac{k}{5}\cdot\frac{1}{16}},\quad\quad\text{and}\quad\quad\frac{|u+v|}{2}+\frac{|u-v|}{4}$
$\displaystyle=\frac{5}{4}\cdot\sqrt{\frac{k}{5}}=\frac{\sqrt{5}}{4}\sqrt{k},$

as required. ∎

#### Final argument in the proof of Theorem 1.3.

Let $u,v\in U$ such that $e=uv$ is an edge of the MST $T$. By the triangle
inequality, the distance from the center of the cube to any point in the ball
$B_{e}$ is at most $\frac{1}{2}|u+v|+\frac{1}{4}|u-v|$. By Lemma 2.4 this
distance is at most $\frac{\sqrt{5}}{4}\sqrt{k}$, thus $\cup_{e\in
T}B_{e}\subset B$, where $B$ is the ball of radius
$\frac{\sqrt{5}}{4}\sqrt{k}=0.559\ldots\cdot\sqrt{k}$ centered at $o$.

The ball packing argument in [7] yields $S_{k}(T)\leq(3\sqrt{k})^{k}$. Using
Lemma 2.4 instead improves this bound to $S_{k}(T)\leq(\sqrt{5k})^{k}$. By
Lemma 2.3 we obtain a Hamiltonian cycle $H$ through $P$ satisfying

$S_{k}(H)\leq\frac{2}{3}\cdot 3^{k}\cdot S_{k}(T)\leq\frac{2}{3}\cdot
3^{k}\cdot(5k)^{k/2}.$ (6)

Taking the $k$-th root completes the proof of item (ii). Note that the only
change in the calculation is replacing a multiplicative factor of $3$ by
$\sqrt{5}$ (in Inequality (2) from [7]). The improvement carries on
proportionally and is reflected in the final bound.

Recall that the traversal of the MST $T$ using the algorithm of Sekanina [23,
24] takes linear time. As such, the running time for computing the TSP tour is
determined by the time to compute $T$. This proves item (iii) and completes
the proof of Theorem 1.3. ∎

An alternative way to verify the upper bound in (6) is by using Theorem 1.2.
The details are left to the reader.

##  3 Hamiltonian cycles for subsets of cube vertices

In this section we consider our problem (the study of extremal values for
Hamiltonian cycles and paths in $[0,1]^{k}$) when the input is restricted to
subsets of cube vertices. Note that this restriction is quite natural, since
all known best constructions are attained or matched by such subsets. We will
use some results on binary codes.

###  3.1 Preparation: binary codes

First we prove an optimization result which will be used multiple times
throughout this paper.

######  Lemma 3.1.

Let $q_{1},q_{2},\ldots,q_{m}\in[0,1]$. Then,

$\displaystyle\sum_{i<j}|q_{i}-q_{j}|^{2}\leq\left\lfloor\frac{m}{2}\right\rfloor\cdot\left\lceil\frac{m}{2}\right\rceil.$

###### Proof.

We prove this result by induction on $m$. The statement holds trivially for
$m=1$ or $m=2$. Let $q_{1},q_{2},\ldots,q_{m}\in[0,1]$ for some $m\geq 3$. We
can assume $0=q_{1}\leq q_{2}\leq\ldots\leq q_{m}=1$. By the induction
assumption,

$\displaystyle\sum_{1<i<j<m}|q_{i}-q_{j}|^{2}\leq\left\lfloor\frac{m-2}{2}\right\rfloor\cdot\left\lceil\frac{m-2}{2}\right\rceil.$

Observe that the maximum of the quadratic function $f(x)=x^{2}+(1-x)^{2}$ over
the interval $[0,1]$ is obtained at $x=0$ or $x=1$. Thus,
$|q_{1}-q_{j}|^{2}+|q_{m}-q_{j}|^{2}=q_{j}^{2}+(1-q_{j})^{2}\leq 1$ for
$j\in\\{2,\ldots,m-1\\}$. Therefore,

$\displaystyle\sum_{i<j}|q_{i}-q_{j}|^{2}$
$\displaystyle=|q_{1}-q_{m}|^{2}+\sum_{1<j<m}(|q_{1}-q_{j}|^{2}+|q_{m}-q_{j}|^{2})+\sum_{1<i<j<m}|q_{i}-q_{j}|^{2}$
$\displaystyle\leq
1+(m-2)+\left\lfloor\frac{m-2}{2}\right\rfloor\cdot\left\lceil\frac{m-2}{2}\right\rceil=\left\lfloor\frac{m}{2}\right\rfloor\cdot\left\lceil\frac{m}{2}\right\rceil,$

completing the proof of this lemma. ∎

######  Lemma 3.2.

Let $\delta,\gamma>0$, and $k_{1},k_{2}$ be non-negative integers. Let
$X\subseteq[0,\delta]^{k_{1}}\times[0,\gamma]^{k_{2}}$ be a finite set of size
$|X|\geq m$. Then there exists two distinct points $p,q\in X$ such that

$|p-q|^{2}\leq\frac{\lfloor\frac{m}{2}\rfloor\lceil\frac{m}{2}\rceil}{\binom{m}{2}}\,(\delta^{2}k_{1}+\gamma^{2}k_{2}).$

###### Proof.

Select arbitrary $m$ points $p_{1},p_{2},\ldots,p_{m}$ from $X$. By applying
Lemma 3.1 and scaling we obtain

$\displaystyle\sum_{i<i^{\prime}}|p_{{i}_{j}}-p_{{i^{\prime}}_{j}}|^{2}$
$\displaystyle\leq\left\lfloor\frac{m}{2}\right\rfloor\cdot\left\lceil\frac{m}{2}\right\rceil\cdot\delta^{2}\quad\quad\text{for
every $j\in[k_{1}]$, and}$ (7)
$\displaystyle\sum_{i<i^{\prime}}|p_{{i}_{j}}-p_{{i^{\prime}}_{j}}|^{2}$
$\displaystyle\leq\left\lfloor\frac{m}{2}\right\rfloor\cdot\left\lceil\frac{m}{2}\right\rceil\cdot\gamma^{2}\quad\quad\text{for
every $j\in[k_{1}+k_{2}]\setminus[k_{1}]$.}$ (8)

By summing up the inequalities (7) and (8), we obtain

$\displaystyle\sum_{i<i^{\prime}}|p_{{i}}-p_{{i^{\prime}}}|^{2}\leq\left\lfloor\frac{m}{2}\right\rfloor\cdot\left\lceil\frac{m}{2}\right\rceil\cdot(\delta^{2}k_{1}+\gamma^{2}k_{2}).$

Thus, by averaging over all pairs of points, the minimizing pair satisfies the
claimed inequality. ∎

Applying Lemma 3.2 with $\delta=\gamma=1$, $k_{1}=k$ and $k_{2}=0$,
immediately yields the following symmetric version.

######  Lemma 3.3.

Let $X\subseteq[0,1]^{k}$ of size $|X|\geq m\geq 3$. Then there exist two
distinct points $p,q\in X$ such that

$|p-q|^{2}\leq\frac{\lfloor\frac{m}{2}\rfloor\cdot\lceil\frac{m}{2}\rceil}{{m\choose
2}}\cdot k.$

Let $A(k,d)$ denote the maximum cardinality of a binary code of length $k$
with minimum distance $d$. We recall the following fact [28]:

######  Lemma 3.4.

(Singleton bound). $A(k,d)\leq 2^{k-d+1}$.

We need the following improvement.

######  Lemma 3.5.

If $d<\frac{2}{3}k$, then $A(k,d)\leq 2^{k-\frac{3}{2}d+2}$.

###### Proof.

Towards contradiction, assume that there exists $X\subseteq\\{0,1\\}^{k}$ of
size $|X|>2\cdot 2^{k-\frac{3}{2}d+1}$ such that $|p-q|^{2}\geq d$ for every
$p,q\in X$. By the pigeonhole principle, there exists $p,q,r\in X$ which
coincide on the first $\lfloor k-\frac{3}{2}d+1\rfloor$ coordinates. By Lemma
3.3, applied with $m=3$ to the last $\lceil\frac{3}{2}d\rceil-1$ coordinates,
we get that

$\displaystyle\min\\{|p-q|^{2},|p-r|^{2},|r-q|^{2}\\}\leq\frac{2}{3}\left(\left\lceil\frac{3}{2}d\right\rceil-1\right)<d,$

a contradiction. ∎

######  Lemma 3.6.

Let $j\in[k]$. The number of edges $e\in F$ satisfying $|e|^{2}\geq j$ is less
than $A(k,j)$.

###### Proof.

Let $\ell$ be the smallest integer such that $|e_{\ell}|^{2}\geq j$. The
number of edges $e\in F$ satisfying $|e|^{2}\geq j$ is less than the number of
components in $F_{\ell}$, which is $n-\ell$. Let $P_{\ell}\subseteq X$ be a
set containing one endpoint of each path in $F_{\ell}$. The set $P_{\ell}$ is
a binary code of length $k$ with minimum distance $j$. Thus, the number of
edges $e\in F$ satisfying $|e|^{2}\geq j$ is less than $A(k,j)$. ∎

###  3.2 Building a path greedily

In the proofs of some of our results we will analyze a greedy algorithm which
takes a discrete point set $X\subseteq[0,1]^{k}$ of size $|X|=n$ as an input
and creates a Hamiltonian path $F$ through $X$. It processes the point pairs
in nondecreasing order of distance and maintains a collection of paths.

Algorithm 1: Initially, set $F_{0}$ to be the empty graph on $X$. For
$i\in[n-1]$, let $e_{i}$ be an edge of smallest weight among all edges
$e\not\in F_{i-1}$ which satisfy that $F_{i-1}+e$ is a vertex-disjoint union
of paths. Set $F_{i}:=F_{i-1}+e_{i}$. Then, $F:=F_{n-1}$ is a Hamiltonian
path.

#### Proof of Theorem 1.4.

If $|X|=2$, the statement holds trivially. Assume $n:=|X|\geq 3$. Let $F$ be
the Hamiltonian path created by Algorithm 1. We partition the edges $e\in F$
into four classes.

  1. 1.

_short_ edges: $|e|^{2}\leq\frac{k}{5}$.

  2. 2.

_medium_ edges: $\frac{k}{5}<|e|^{2}\leq\frac{3k}{5}$.

  3. 3.

_long_ edges: $\frac{3k}{5}<|e|^{2}\leq\frac{2k}{3}$.

  4. 4.

_very long_ edges: $\frac{2k}{3}<|e|^{2}$.

Denote by $F^{s},F^{m},F^{l},f^{vl}$ the subgraphs of $F$ containing all
short, medium, long and very long edges, respectively. They partition $F$ and
thus $S_{k}(F)=S_{k}(F^{s})+S_{k}(F^{m})+S_{k}(F^{l})+S_{k}(F^{vl})$. We will
provide upper bounds for the four contributions separately.

Since $n\leq 2^{k}$, the number of short edges is trivially at most $2^{k}$.
Thus, $S_{k}(F^{s})\leq 2^{k}\left(\sqrt{\frac{k}{5}}\right)^{k}$.

Now, we estimate $S_{k}(F^{m})$. Let $j$ be an integer satisfying
$\frac{k}{5}<j\leq\frac{3k}{5}$. The number of edges $e\in F$ satisfying
$|e|^{2}\geq j$ is less than $A(k,j)\leq 2^{k-\frac{3}{2}j+2}$ by Lemmas 3.5
and 3.6. Therefore,

$S_{k}(F^{m})\leq\sum_{j=\left\lceil\frac{k}{5}\right\rceil}^{\left\lfloor\frac{3k}{5}\right\rfloor}2^{k-\frac{3}{2}j+2}\left(\sqrt{j}\right)^{k}\leq
4\cdot\left(\left\lfloor\frac{3k}{5}\right\rfloor-\left\lceil\frac{k}{5}\right\rceil\right)\cdot\left(0.842\sqrt{k}\right)^{k}\leq\frac{8k}{5}\cdot\left(0.842\sqrt{k}\right)^{k}.$

Here we used that the function $f(x)=2^{1-3x/2}\sqrt{x}$, where $x\geq 0$, is
maximized for $x=\frac{1}{\log(8)}$ and thus $2^{1-3x/2}\sqrt{x}\leq 0.842$.

Next, we estimate $S_{k}(F^{l})$. The number of edges $e\in F$ satisfying
$|e|^{2}>\frac{3k}{5}$ is less than $A(k,\lfloor\frac{3k}{5}\rfloor+1)\leq 4$
by Lemma 3.3, applied with $m=5$ and by Lemma 3.6. Therefore,

$S_{k}(F^{l})\leq 3\cdot\left(\sqrt{\frac{2}{3}k}\right)^{k}.$

Last, we estimate $S_{k}(F^{vl})$. The number of edges $e\in F$ satisfying
$|e|^{2}>\frac{2k}{3}$ is less than $A(k,\lfloor\frac{2k}{3}\rfloor+1)\leq 2$
by Lemma 3.3, applied with $m=3$ and Lemma 3.6. Thus, there is at most one
very long edge $e$ in $F$. This very long edge has length at most
$|e|\leq\sqrt{k-1}$ by the following argument. Consider the last step of the
greedy algorithm, when the last two paths, call them $P_{1}$ and $P_{2}$, are
being joined. Since $|X|\geq 3$, one of them, say $P_{1}$, contains at least
two vertices. An endpoint of the path $P_{2}$ has distance at most
$\sqrt{k-1}$ to one of the endpoints of $P_{1}$, since not both endpoints can
be opposite on the cube. Thus, $|e|\leq\sqrt{k-1}$. We get
$S_{k}(F^{vl})\leq\sqrt{k-1}^{k}$.

Adding up the four contributions to $S_{k}(F)$ yields

$\displaystyle S_{k}(F)$
$\displaystyle=S_{k}(F^{s})+S_{k}(F^{m})+S_{k}(F^{l})+S_{k}(F^{vl})$
$\displaystyle\leq
2^{k}\left(\sqrt{\frac{k}{5}}\right)^{k}+\frac{8k}{5}\cdot\left(0.842\sqrt{k}\right)^{k}+3\cdot\left(\sqrt{\frac{2}{3}k}\right)^{k}+\left(\sqrt{k-1}\right)^{k}$
$\displaystyle=\left(\sqrt{k}\right)^{k}\left(\left(\frac{2}{\sqrt{5}}\right)^{k}+\frac{8k}{5}\cdot
0.842^{k}+3\cdot\left(\sqrt{\frac{2}{3}}\right)^{k}+\left(\sqrt{\frac{k-1}{k}}\right)^{k}\right)$
$\displaystyle<\left(\sqrt{k}\right)^{k},$ (9)

where the last inequality holds for $k$ sufficiently large. We used the fact
that $\left(\sqrt{\frac{k-1}{k}}\right)^{k}$ converges to $e^{-1/2}$. Let $H$
be the Hamiltonian cycle obtained from $F$ by connecting the two endpoints.
Then

$S_{k}(H)\leq S_{k}(F)+\left(\sqrt{k}\right)^{k}\leq
2\left(\sqrt{k}\right)^{k}.\qed$

We remark that the proof of Theorem 1.4 works for $k_{0}=29$, and no attempt
to optimize the proof to hold for smaller values of $k_{0}$ has been made. The
last inequality in (3.2) is strict. Thus, Theorem 1.4 is tight only for
$|X|=2$.

##  4 Hamiltonian cycles: asymptotic upper bounds

In this section we prove Theorems 1.5, 1.6 and 1.7.

###  4.1 Preparation

######  Lemma 4.1.

Let $0<\alpha<1$ and $Y\subseteq[0,1]^{k}$ such that $|u-v|>\alpha\sqrt{k}$
for every two distinct points $u,v\in Y$. Let $m\in\mathbb{N}$. Then, $|Y|\leq
2m\cdot\left\lceil\frac{\sqrt{\frac{1}{2}\left(1+\frac{1}{2m-1}\right)}}{\alpha}\right\rceil^{k}$.

###### Proof.

Let
$\beta=\left\lceil\frac{\sqrt{\frac{1}{2}\left(1+\frac{1}{2m-1}\right)}}{\alpha}\right\rceil$.
Assume that $|Y|>2m\cdot\beta^{k}$. Partition the unit box $[0,1]^{k}$ into
$\beta^{k}$ boxes $B_{1},B_{2},\ldots,B_{\beta^{k}}$ as follows: We split up
$[0,1]$ into $\beta$ disjoint consecutive intervals of length $\beta^{-1}$
each. This gives in total $\beta^{k}$ boxes.

Since $|Y|>2m\cdot\beta^{k}$, there exists a box $B_{j}$ such that at least
$2m$ points from $Y$ are contained in it. By Lemma 3.2, applied with
$\gamma=\beta,\delta=0,k_{1}=k$ and $k_{2}=0$, there exist $p,q\in B_{j}\cap
Y$ such that
$|p-q|^{2}\leq\frac{1}{2}\left(1+\frac{1}{2m-1}\right)\beta^{-2}k$. We
conclude

$\displaystyle\alpha^{2}k<|p-q|^{2}\leq\frac{1}{2}\left(1+\frac{1}{2m-1}\right)\beta^{-2}k,\quad\text{implying}\quad\alpha<\sqrt{\frac{1}{2}\left(1+\frac{1}{2m-1}\right)}\beta^{-1}.$

However, since
$\beta=\left\lceil\frac{\sqrt{\frac{1}{2}\left(1+\frac{1}{2m-1}\right)}}{\alpha}\right\rceil$,
we have
$\alpha<\sqrt{\frac{1}{2}\left(1+\frac{1}{2m-1}\right)}\beta^{-1}\leq\alpha$,
a contradiction. ∎

The following lemma is a version of Lemma 4.1 which improves the bound in a
certain range of $\alpha$.

######  Lemma 4.2.

Let $\sqrt{\frac{100}{1791}}<\alpha<\sqrt{\frac{100}{199}}$ and
$Y\subseteq[0,1]^{k}$ such that $|u-v|>\alpha\sqrt{k}$ for every two distinct
points $u,v\in Y$. Then,

$\displaystyle|Y|\leq 600\cdot
3^{\frac{9}{8}\left(1-\frac{199}{100}\alpha^{2}\right)k}.$

###### Proof.

Let $a=\frac{9}{8}(1-\frac{199}{100}\alpha^{2})$. Note that $0<a<1$. Partition
the unit box $[0,1]^{k}$ into $3^{\lceil ak\rceil}$ boxes
$B_{1},B_{2},\ldots,B_{3^{\lceil ak\rceil}}$ as follows: Let
$I=\\{1,2,\ldots,\lceil ak\rceil\\}\subseteq[k]$. For the coordinates in $I$,
we split up $[0,1]$ into 3 disjoint consecutive
$[0,1]=[0,\frac{1}{3})\cup[\frac{1}{3},\frac{2}{3})\cup[\frac{2}{3},1]$
intervals of length $\frac{1}{3}$ each. If $|Y|>200\cdot 3^{\lceil ak\rceil}$,
then there exists a box $B_{j}$ such that at least 200 points from $Y$ are
contained in it. By Lemma 3.2, applied with $m=200$, $\delta=\frac{1}{3}$,
$\gamma=1$, $k_{1}=\lceil ak\rceil$ and $k_{2}=k-k_{1}$, there exist $p,q\in
B_{j}\cap Y$ such that

$\displaystyle\frac{|p-q|^{2}}{k}\leq\frac{100}{199}\left(\frac{1}{3}\right)^{2}\frac{\lceil
ak\rceil}{k}+\frac{100}{199}\frac{k-\lceil
ak\rceil}{k}\leq\frac{100}{199}-\frac{8}{9}\frac{100}{199}a=\alpha^{2},$

contradicting $\alpha^{2}k<|p-q|^{2}$. We conclude that

$|Y|\leq 200\cdot 3^{\lceil ak\rceil}\leq 600\cdot 3^{ak}=600\cdot
3^{\frac{9}{8}\left(1-\frac{199}{100}\alpha^{2}\right)k}.\qed$

######  Lemma 4.3.

Let $0<\alpha<0.99$. There exists $k_{0}$ such that for all integers $k\geq
k_{0}$ the following holds. Let $Y\subseteq[0,1]^{k}$ such that
$|u-v|>\alpha\sqrt{k}$ for every two distinct points $u,v\in Y$. Then
$|Y|\alpha^{k}\leq 0.999^{k}$ for $k$ sufficiently large.

###### Proof.

First, assume $\sqrt{\frac{100}{199}}<\alpha<0.99$. Then $|Y|\leq 200$ by
Lemma 3.3, applied with $m=200$. Thus,

$\displaystyle|Y|\alpha^{k}\leq 200\alpha^{k}\leq 0.999^{k}.$

Next, assume $0.29\leq\alpha\leq\sqrt{\frac{100}{199}}$. Then by Lemma 4.2,

$\displaystyle|Y|\alpha^{k}\leq
600\cdot\left(3^{\frac{9}{8}\left(1-\frac{199}{100}\alpha^{2}\right)}\alpha\right)^{k}\leq
0.999^{k}.$

Finally, assume $0<\alpha\leq 0.29$. Then by Lemma 4.1, applied with $m=100$,

$|Y|\alpha^{k}\leq
200\left(\left\lceil\frac{\sqrt{\frac{1}{2}\left(1+\frac{1}{199}\right)}}{\alpha}\right\rceil\alpha\right)^{k}\leq
200\left(\sqrt{\frac{100}{199}}+\alpha\right)^{k}\leq 0.999^{k}.\qed$

###  4.2 Proofs of Theorems 1.5, 1.6, and 1.7

First, we quickly demonstrate how Lemma 3.3 implies Theorem 1.7.

#### Proof of Theorem 1.7.

Let $X\subseteq[0,1]^{k}$ be a point set of size $n$. We run Algorithm 1 from
Section 3.2. Let $F_{i}$ be the collection of paths at the $i$-th step, let
$e_{i}$ be the edge added in the $i$-th step, and let $F=F_{n-1}$ be the final
Hamiltonian path.

We claim that $|e_{i}|\leq\sqrt{\frac{2}{3}k}$ for $i\leq n-2$. Let
$e_{i}=xy$. The vertices $x$ and $y$ are endpoints of two different paths in
$F_{i-1}$. Since $F_{i-1}$ has at least $n-(i-1)\geq n-(n-2-1)=3$ components,
there exists a component containing neither $x$, nor $y$. Let $z\in X$ be an
endpoint of the path forming this component. Since $e_{i}=xy$ was chosen in
step $i$, but $xz$ and $yz$ were not, we have $|xy|\leq|xz|$ and
$|xy|\leq|yz|$. By applying Lemma 3.3 to the set $\\{x,y,z\\}$, we get that
$|e_{i}|=|xy|\leq\sqrt{\frac{2}{3}k}$. Note that $|e_{n-1}|\leq\sqrt{k}$
trivially.

Now, let $f=ab$ be the edge where $a$ and $b$ are the two endpoints of the
final path $F$. Set $H=F+f$ to be the Hamiltonian cycle when $f$ is added to
$F$. Since $|f|\leq\sqrt{k}$ trivially, we get

$\displaystyle S_{k}(H)$ $\displaystyle=\sum_{e\in
H}|e|^{k}=|f|^{k}+|e_{n-1}|^{k}+\sum_{i=1}^{n-2}|e_{i}|^{k}\leq
2\left(\sqrt{k}\right)^{k}+(n-2)\left(\sqrt{\frac{2}{3}k}\right)^{k}.$

Consequently,

$s_{k}^{\texttt{HC}}(n)\leq s_{k}(H)\leq 2^{1/k}\sqrt{k}\ (1+o_{k}(1)).\qed$

#### Proof of Theorem 1.5.

Let $k$ be sufficiently large and let $X\subseteq[0,1]^{k}$ be a finite point
set. Set

$\displaystyle\ell:=\left\lceil\log_{1+\frac{1}{k}}\left(0.9k^{\frac{3}{4}}\right)\right\rceil=O(k\log
k)\quad\quad\text{and}\quad\quad
a_{i}:=\frac{(1+\frac{1}{k})^{i}}{k^{\frac{3}{4}}}$

for integers $i$, $0\leq i\leq\ell$. Note that

$\displaystyle\frac{a_{i+1}}{a_{i}}=1+\frac{1}{k}\ \text{for}\
i\in\\{0,1,\dots,\ell-1\\},\quad\text{and}\quad
a_{0}<a_{1}<a_{2}<\cdots<a_{\ell-1}\leq 0.9\leq a_{\ell}.$

Construct a minimum spanning tree $T$ on vertex set $X$ by successively
joining points from $X$ at minimal distance from each other, given the new
edge does not create a cycle. For $0\leq i\leq\ell$, let $F_{i}$ be the forest
with vertex set $X$ and edges $e\in T$ such that $|e|\leq a_{i}\sqrt{k}$.
Then, $F_{0}\subseteq F_{1}\subseteq\dots\subseteq F_{\ell}=T$ since the
sequence $(a_{i})$ is increasing. If $x,y\in X$ are in different components of
$F_{i}$, then $|x-y|>a_{i}\sqrt{k}$.

We have $a_{0}=k^{-3/4}$. For an edge $e=xy\in F_{0}$, let $B_{e}$ be the open
ball of radius $|e|/4$ and center $\frac{1}{2}(x+y)$. Since $F_{0}\subseteq
T$, by Lemma 2.1, the balls $B_{e}$, $e\in F_{0}$ are disjoint. Also, $|e|\leq
a_{0}\sqrt{k}=k^{-1/4}$. Denote by $V_{k}$ for the volume of the
$k$-dimensional unit ball. It is well-known that

$V_{k}=\begin{cases}\dfrac{\pi^{k/2}}{(k/2)!}&{\rm if\ }k\ {\rm is\
even},\vskip 6.0pt plus 2.0pt minus 2.0pt\\\
\dfrac{2^{k}\cdot\pi^{(k-1)/2}\,((k-1)/2)!}{k!}&{\rm if\ }k\ {\rm is\
odd}.\end{cases}$

By Stirling’s approximation, $V_{k}\sim\frac{1}{\sqrt{k\pi}}(\frac{2\pi
e}{k})^{k/2}$. Since $\bigcup_{e\in
F_{0}}B_{e}\subseteq[-k^{-1/4},1+k^{-1/4}]$, we have

$\displaystyle\sum_{e\in
F_{0}}\left(\frac{|e|}{4}\right)^{k}V_{k}\leq((1+2k^{-1/4}))^{k},\quad\text{and
thus}\quad\sum_{e\in
F_{0}}|e|^{k}\leq\frac{4^{k}(1+2k^{-1/4})^{k}}{V_{k}}\leq(0.97\sqrt{k})^{k},$

for $k$ sufficiently large. Now, let $i\in\\{0,1,\ldots,\ell-1\\}$. Let
$Y\subseteq X$ be a set of vertices containing exactly one vertex from every
component of $F_{i}$. Then $|y-y^{\prime}|>a_{i}\sqrt{k}$ for every pair
$y\neq y^{\prime}\in Y$, and $|F_{i+1}\setminus F_{i}|\leq|Y|-1$. By Lemma 4.3
we have $a_{i}^{k}|Y|\leq 0.999^{k}$ for $i\leq\ell$. Thus,

$\displaystyle\sum_{e\in F_{i+1}\setminus
F_{i}}|e|^{k}\leq(a_{i+1}\sqrt{k})^{k}|Y|=(a_{i}\sqrt{k})^{k}|Y|\left(1+\frac{1}{k}\right)^{k}\leq
3\cdot(0.999\sqrt{k})^{k},$

for $i\leq\ell$. Therefore,

$\displaystyle\sum_{e\in F_{\ell}}|e|^{k}$ $\displaystyle=\sum_{e\in
F_{0}}|e|^{k}+\sum_{i=0}^{\ell-1}\sum_{e\in F_{i+1}\setminus
F_{i}}|e|^{k}\leq\left(0.97\sqrt{k}\right)^{k}+3\ell\cdot(0.999\sqrt{k})^{k},$

for $k$ sufficiently large. If the forest $F_{\ell}$ consist of at least three
components then three points $p,q,r\in X$, from different components each,
have pairwise distance at least $0.9\sqrt{k}\geq\sqrt{\frac{2}{3}k}$. This
contradicts Lemma 3.3. Therefore, $F_{\ell}$ has at most 2 components and thus
there is at most one edge $f$ in $T$ which is not in $F_{\ell}$. We conclude

$\displaystyle\sum_{e\in T}|e|^{k}=\sum_{e\in
F_{\ell}}|e|^{k}+|f|^{k}\leq\left(\sqrt{k}\right)^{k}(1+o_{k}(k^{-1})),$

which implies that for the family of minimum spanning trees, we have
$s_{k}^{\texttt{ST}}\leq\sqrt{k}\ (1+o_{k}(1))$, completing the proof of
Theorem 1.5. ∎

We remark that by applying Lemma 2.3 to $T$, there exists a Hamiltonian cycle
$H$ on vertex set $X$ satisfying

$\displaystyle\sum_{e\in H}|e|^{k}\leq\frac{2}{3}\cdot 3^{k}\sum_{e\in
T}|e|^{k}\leq\left(3\sqrt{k}\right)^{k}(1+o_{k}(k^{-1})),$

implying that for the family of Hamiltonian cycles, we have
$s_{k}^{\texttt{HC}}\leq 3\sqrt{k}\ (1+o_{k}(1))$.

#### Proof of Theorem 1.6.

Create a forest $F$ by successively joining points from $X$ at minimal
distance from each other, given the new edge $e$ does not create a cycle and
satisfies $|e|\leq k^{-1/4}$. This process stops when there is no such edge
left. Let the trees $T_{1},\ldots,T_{N}$ be the components of $F$. Every two
vertices from different $T_{i}$’s have pairwise distance at least $k^{-1/4}$.

For an edge $e=xy\in F$, let $B_{e}$ be the open ball of radius $|e|/4$ and
center $\frac{1}{2}(x+y)$. By Lemma 2.1, the balls $B_{e}$, $e\in F$ are
disjoint. Also, $|e|\leq k^{-\frac{1}{4}}$. We have $\bigcup_{e\in
F_{0}}B_{e}\subseteq[-k^{-1/4},1+k^{-1/4}]$. Writing $V_{k}$ for the volume of
the $k$-dimensional unit ball, we have

$\displaystyle\sum_{e\in
F}\left(\frac{|e|}{4}\right)^{k}V_{k}\leq((1+2k^{-1/4}))^{k}\quad\text{and
thus}\quad\sum_{e\in
F}|e|^{k}\leq\frac{4^{k}(1+2k^{-1/4})^{k}}{V_{k}}\leq(0.97\sqrt{k})^{k},$

for $k$ sufficiently large. Since the trees $T_{1},\ldots,T_{N}$ decompose the
edge set of the forest $F$, we have

$\displaystyle\sum_{i=1}^{N}\sum_{e\in T_{i}}|e|^{k}=\sum_{e\in
F}|e|^{k}\leq(0.97\sqrt{k})^{k}.$

By Lemma 2.3, for each $i\in[N]$, there exists a Hamiltonian cycle $H_{i}$ on
$V(T_{i})$ such that

$\displaystyle\sum_{e\in H_{i}}|e|^{k}\leq 3^{k}\sum_{e\in T_{i}}|e|^{k}.$

Let $F_{0}$ be the collection of paths obtained taking of the union of all
$H_{i}$, and removing an edge from each cycle. Then

$\displaystyle\sum_{e\in F_{0}}|e|^{k}\leq\sum_{i=1}^{N}\sum_{e\in
H_{i}}|e|^{k}\leq 3^{k}\sum_{i=1}^{N}\sum_{e\in
T_{i}}|e|^{k}\leq(2.91\sqrt{k})^{k}.$

Now, as in Algorithm 1 from Section 3.2, add edges of minimum weight such that
in each step we maintain a collection of paths. Similarly, as in the proof of
Theorem 1.7 and by using Lemma 4.3, we end up with a single path $Q$ still
satisfying

$\displaystyle\sum_{e\in Q}|e|^{k}\leq(2.91\sqrt{k})^{k}(1+o_{k}(1)).$

Adding one final edge $f$ of weight at most $|f|\leq\sqrt{k}$ we obtain a
Hamiltonian cycle with the desired properties. ∎

##  5 Concluding Remarks

The upper bounds we obtained on the lengths of Hamiltonian cycles have the
following implications for the existence of perfect matchings whose cost is
bounded from above by a constant (depending on $k$). For example, Theorems 1.3
and 1.4 have the following implications. The proofs of Corollary 5.1 and that
of Corollary 5.2 are analogous to the proof of Corollary 5.4 below.

######  Corollary 5.1.

Given $n$ points in $[0,1]^{k}$, where $k\geq 3$, and $n$ is even, there
exists a perfect matching $M$ of the $n$ points such that $\left(\sum_{e\in
M}|e|^{k}\right)^{1/k}\leq
3\sqrt{5}\left(\frac{1}{3}\right)^{1/k}\cdot\sqrt{k}$. The matching $M$ can be
computed in time proportional to that needed for computing a MST of the
points, in particular, in subquadratic time.

######  Corollary 5.2.

There exists an integer $k_{0}$ such that for all $k\geq k_{0}$ the following
holds. If $X$ is any even-size subset of vertices of $\\{0,1\\}^{k}$, then
there exists a perfect matching $M$ of $X$ such that $s_{k}(M)\leq\sqrt{k}$.
This bound is best possible.

Recall that a MST of $n$ points in $\mathbb{R}^{k}$ (with respect to Euclidean
distances) can be computed in $O\left(n^{2-\frac{2}{\lceil
k/2\rceil+1}+\varepsilon}\right)$ time, for any $\varepsilon>0$ [1]. Note also
that
$\lim_{k\to\infty}\left(\frac{2}{3}\right)^{1/k}=\lim_{k\to\infty}\left(\frac{1}{3}\right)^{1/k}=1$.

We also deduce the following related results (formulated here for the planar
case, $k=2$.)

######  Corollary 5.3.

Let $x_{1},\ldots,x_{n}$ be $n\geq 2$ points in the unit square. Let $d_{i}$
be the distance between $x_{i}$ and its nearest point (other than $x_{i}$).
Then the following inequality holds: $\sum_{i=1}^{n}d_{i}^{2}\leq 4$.

###### Proof.

Consider a Hamiltonian cycle, say $x_{1},\ldots,x_{n}$, whose cost $S_{2}(H)$
is at most $4$. The distance from $x_{i}$ to its nearest point is at most
$|x_{i}-x_{i+1}|$, for $i=1,\ldots,n$. By squaring the $n$ inequalities and
adding them up, the claimed inequality follows. ∎

An alternative proof of Corollary 5.3 can be found in [27, Problem G.27].

######  Corollary 5.4.

Let $x_{1},\ldots,x_{n}$ be $n\geq 2$ points in the unit square, where $n$ is
even. Then there exists a perfect matching $M$ such that $\sum_{e\in
M}|e|^{2}\leq 2$. This bound is the best possible.

###### Proof.

Consider a Hamiltonian cycle, say $H=x_{1},\ldots,x_{n}$, whose cost
$S_{2}(H)$ is at most $4$. $H$ can be decomposed into two perfect matchings,
one of which has a cost at most $2$, as required.

The lower bounds for $n=2$ and $n=4$ are immediate (see Figure 1). For every
even $n\geq 6$ and $\varepsilon>0$, there are $n$ points (in the neighborhoods
of the four corners of the square) such that $\sum_{e\in M}|e|^{2}\geq
2-\varepsilon$. ∎

We have improved the upper bound of Bollobás and Meir [7] by more than 25
percent in the exact formulation and by more than 67 percent in the asymptotic
formulation. Apart from some doubt concerning the values of
$s_{3}^{\texttt{HC}}(n)$ and $s_{4}^{\texttt{HC}}(n)$, we think that their
lower bound gives the right answer for every higher dimension. In view of
Theorem 1.3 (i) we adjust their conjecture as follows:

######  Conjecture 5.5.

For Hamiltonian cycles, the following equalities hold:

$s_{k}^{\texttt{HC}}=\begin{cases}2^{7/6},&\text{ for }k=3\\\
2^{1/k}\cdot\sqrt{k},&\text{ for }k\geq 4.\end{cases}$

#### Hamiltonian path.

If one was looking for a Hamiltonian path, instead of a Hamiltonian cycle,
then the $2$-point extremal lower bound example (given by a cube diagonal)
looses a factor of $2$ (or with scaling $2^{1/k}$); and so the question
arises: is it still the best example, or maybe only for large $k$? Analogous
to the situation for Hamiltonian paths, we think that there is a threshold
value for $k$ after which the extremal examples stabilizes at the $2$-point
example. The threshold values for cycles and paths seem to differ, see
Conjecture 5.6 below.

The current upper bound proofs essentially remain the same as for Hamiltonian
cycles, with the change that the last edge is not needed. Some upper bounds
remain unchanged, and others do improve. In particular,
$s_{2}^{\texttt{HP}}\leq s_{2}^{\texttt{HC}}=2$ remains unchanged, whereas
$s_{2}^{\texttt{HP}}\geq\sqrt{3}$ is implied by the two extremal examples in
Figure 1 (left and right).

From the other direction, for small values of $k$ consider once again a binary
code of length $k$ with minimum distance $2$ given by the set of all
$x\in\\{0,1\\}^{k}$ with an even number of $1$’s. It yields the values
specified below.

######  Conjecture 5.6.

For Hamiltonian paths, the following equalities hold:

$s_{k}^{\texttt{HP}}=\begin{cases}\sqrt{3},&\text{ for }k=2\\\
\left(2^{k-1}-1\right)^{1/k}\cdot\sqrt{2},&\text{ for }k=3,4,5,6\\\
\sqrt{k},&\text{ for }k\geq 7.\end{cases}$

#### Further improvement.

One might wonder where the next possible improvement is? We feel that it is in
Lemma 2.2: It states that there is a Hamiltonian cycle that each edge of the
cycle is using at most 3 tree edges, yet the average usage is slightly less
than 2. If it was true that every tree edge is used at most twice, then we
would get a 2/3 factor improvement in the upper bound. However, the example of
a tree with edges $ab,bc,cd,de,cf,fg$ shows that this is not the case. Still,
it is likely that there is a way to gain more in a tree to cycle or path
conversion.

#### A different version.

We conclude with yet another version of the problem. Instead of the unit cube
$[0,1]^{k}\subset\mathbb{R}^{k}$, let the diameter of the point set be at most
$1$: That is, ${\rm diam}(X)\leq 1$, where $X\subset\mathbb{R}^{k}$ and
$|X|=n$. What are the extremal values of the (say, unscaled) costs of a
shortest Hamiltonian cycle (and path) for $n$ points in $\mathbb{R}^{k}$ under
this constraint? Are they given by the vertices of a unit simplex in
$\mathbb{R}^{k}$ ($k+1$ and $k$, respectively)?

## References

  * [1] Pankaj K. Agarwal, Herbert Edelsbrunner, and Otfried Schwarzkopf, Euclidean minimum spanning trees and bichromatic closest pairs, _Discrete & Computational Geometry_ 6 (1991), 407–422.
  * [2] Thomas Andreae, On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality, _Networks_ 38(2) (2001), 59–67.
  * [3] Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, _Journal of the ACM_ 45(5) (1998), 753–782.
  * [4] 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.
  * [5] Michael Bender and Chandra Chekuri, Performance guarantees for the TSP with a parameterized triangle inequality, _Information Processing Letters_ 73(1-2) (2000), 17–21.
  * [6] Béla Bollobás, _The Art of Mathematics — Coffee Time in Memphis_ , Cambridge University Press, 2006.
  * [7] Béla Bollobás and Amram Meir, A travelling salesman problem in the $k$-dimensional unit cube, _Operations Research Letters_ 11(1) (1992), 19–21.
  * [8] Nicos Christofides, Worst-case analysis of a new heuristic for the Traveling Salesman Problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, 1976.
  * [9] Mark de Berg, Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, and Alexander Wolff, The Traveling Salesman Problem under squared Euclidean distances, in _Proc. of the 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010_ , LIPIcs series, vol. 5, pp. 239–250.
  * [10] László Fejes Tóth, Über einen geometrischen Satz, _Mathematische Zeitschrift_ 46(1) (1940), 83–85.
  * [11] Leonard Few, The shortest path and shortest road through $n$ points, _Mathematika_ 2 (1955), 141–144.
  * [12] Stefan Funke, Sören Laue, Zvi Lotker, and Rouven Naujoks, Power assignment problems in wireless communication: Covering points by disks, reaching few receivers quickly, and energy-efficient traveling salesman tours, _Ad Hoc Networks_ 9(6) (2011), 1028–1035.
  * [13] Anna R. Karlin, Nathan Klein, and Shayan O. Gharan, A (slightly) improved approximation algorithm for metric TSP, _Proc. 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)_ Virtual Event, Italy, June 2021, pp. 32–45.
  * [14] Howard J. Karloff, How long can a Euclidean traveling salesman tour be? _SIAM Journal of Discrete Mathematics_ 2 (1989), 91–99.
  * [15] Gady Kozma, Zvi Lotker, and Gideon Stupp, The minimal spanning tree and the upper box dimension, _Proceedings of the American Mathematical Society_ 134(4) (2006), 1183–1187.
  * [16] Joseph S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, $k$-MST, and related problems, _SIAM Journal on Computing_ 28(4) (1999), 1298–1309.
  * [17] Tobias Mömke, An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality, _Information Processing Letters_ , 115(11) (2015), 866–871.
  * [18] Shlomo Moran, On the length of optimal TSP circuits in sets of bounded diameter, _Journal of Combinatorial Theory, Series B_ 37(2) (1984), 113–141.
  * [19] William O. J. Moser, Problems, problems, problems, _Discrete Applied Mathematics_ 31(2) (1991), 201–225.
  * [20] Donald J. Newman, _A Problem Seminar_ , Springer, New York, 1982.
  * [21] Christos H. Papadimitriou and Mihalis Yannakakis, The traveling salesman problem with distances one and two, _Mathematics of Operations Research_ 18(1) (1993), 1–11.
  * [22] Wansoo T. Rhee, On the travelling salesperson problem in many dimensions, _Random Structures & Algorithms_ 3(3) (1992), 227–233.
  * [23] Milan Sekanina, On an ordering of the set of vertices of a connected graph, Publications of the Faculty of Science, University of Brno, 412 (1960), 137–142.
  * [24] Milan Sekanina, On an algorithm for ordering of graphs, _Canadian Mathematical Bulletin_ 14(2) (1971), 221–224.
  * [25] Michael J. Steele, _Probability Theory and Combinatorial Optimization_ , SIAM, Philadelphia, 1997.
  * [26] Kenneth J. Supowit, Edward M. Reingold, and David A. Plaisted, The traveling salesman problem and minimum matching in the unit square, _SIAM Journal on Computing_ 12(1) (1983), 144–156.
  * [27] Gábor J. Székely, _Contests in Higher Mathematics_ , Springer, New York, 1996.
  * [28] Jacobus H. van Lint, Codes, Ch. 16 in _Handbook of Combinatorics_ , Ron Graham, Martin Grötschel, and László Lovász (editors), Elsevier, Amsterdam, 1995, pp. 773–808.
  * [29] Jacobus H. van Lint, _Introduction to Coding Theory_ , Springer, 3rd edition, New York, 1999.
  * [30] Samuel Verblunsky, On the shortest path through a number of points, _Proceedings of the American Mathematical Society_ 2(6) (1951), 904–913.

##  6 Appendix

### Container shapes with a tight bound when $k=2$

A key fact in deriving the tight bound, when $k=2$, for the cycle of $n$
points in the unit square is the following tight bound in a right triangle
[20]; see also [6].

######  Lemma 6.1.

[20] Let $X$ be a set of $n\geq 2$ points in a right triangle $\Delta$ whose
sides are $a\leq b\leq c$. Then there is an extended path connecting the
endpoints of $c$ that visits all points in $X$ and for which $\sum|e|^{2}\leq
c^{2}$. In particular, $X$ admits a Hamiltonian path $P$ for which $\sum_{e\in
P}|e|^{2}\leq c^{2}$. This bound is the best possible.

This result relies on a repeated application of the following simple corollary
of the Cosine Law. It allows one to make shortcuts in a path or cycle at
vertices where the two adjacent edges make an acute angle.

######  Lemma 6.2.

[20] Let $\Delta$ be an triangle whose sides are $a\leq b\leq c$, and let
$\gamma$ be the interior angle opposite to $c$. If $\gamma\leq 90^{\circ}$,
then $c^{2}\leq a^{2}+b^{2}$.

We now exhibit two other container shapes for which we can deduce a tight
bound. Lemma 6.3 below is an extension of Lemma 6.1.

Figure 2: Left: Lemma 6.3. Right: Lemma 6.6.

######  Lemma 6.3.

Let $X$ be a set of $n\geq 2$ points in a non-obtuse triangle $\Delta$ whose
sides are $a\leq b\leq c$. Then there is an extended path connecting the
endpoints of $c$ that visits all points in $\Delta$ and for which
$\sum|e|^{2}\leq a^{2}+b^{2}$. In particular, $X$ admits a Hamiltonian path
$P$ for which $\sum_{e\in P}|e|^{2}\leq a^{2}+b^{2}$. This bound is the best
possible.

###### Proof.

Let the altitude corresponding to $c$ divide $\Delta$ into two right
triangles. Consider the path obtained by concatenating the extended paths for
the two right triangles. Further shortcut the path at the concatenation vertex
by using Lemma 6.2 to obtain a Hamiltonian path $P$ for which $\sum_{e\in
P}|e|^{2}\leq a^{2}+b^{2}$, see Figure 2 (left). The three vertices of
$\Delta$ provide a tight example. ∎

######  Lemma 6.4.

Let $X$ be a set of $n\geq 2$ points in a non-obtuse triangle $\Delta$ whose
sides are $a\leq b\leq c$. Then $X$ admits a Hamiltonian cycle $H$ for which
$\sum_{e\in H}|e|^{2}\leq a^{2}+b^{2}+c^{2}$. This bound is the best possible.

###### Proof.

By Lemma 6.3, $X$ admits a Hamiltonian path $P$ for which $\sum_{e\in
P}|e|^{2}\leq a^{2}+b^{2}$. Connecting the endpoints of this path (via an edge
of length at most $c$) yields a Hamiltonian cycle $H$ for which $\sum_{e\in
H}|e|^{2}\leq a^{2}+b^{2}+c^{2}$. ∎

By Lemma 6.3 and 6.4, we obtain the following corollary.

######  Corollary 6.5.

Let $X$ be a finite point set in in a non-obtuse triangle $\Delta$ whose sides
are $a\leq b\leq c\leq 1$. Then

  1. 1.

$X$ admits a Hamiltonian path $P$ for which $\sum_{e\in P}|e|^{2}\leq 2$.

  2. 2.

$X$ admits a Hamiltonian cycle $H$ for which $\sum_{e\in H}|e|^{2}\leq 3$.

######  Lemma 6.6.

Let $U$ be a unit square centered at $o$ and let $ab$ be one of its four
sides. Let $X$ be a set of $n\geq 2$ points in $V:=U\setminus\Delta{oab}$ ($V$
as a closed set). Then $X$ admits a Hamiltonian path $P$ for which $\sum_{e\in
P}|e|^{2}\leq 3$. This bound is the best possible.

###### Proof.

Subdivide $V$ into two right triangles as shown in Figure 2 (right). Consider
the path obtained by concatenating the extended paths for the two right
triangles. Further shortcut the path by using Lemma 6.2 to obtain a
Hamiltonian path $P$ for which $\sum_{e\in P}|e|^{2}\leq
1^{2}+(\sqrt{2})^{2}=3$. The $4$\- and $5$-point examples in Figure 1 show
that this bound is tight. ∎

### A different version of Theorem 1.7

We remark that the proof of Theorem 1.7 can be extended for point sets of size
$n$, when $n$ is slowly growing in $k$, to obtain an upper bound sharper than
that in Theorem 1.6.

######  Theorem 6.7.

The following bounds are in effect:

  * (i)

If $n\leq 2^{k}+2$, then there exists a Hamiltonian cycle $H$ such that

$S_{k}(H)\leq\left(2+\left(\frac{8}{3}\right)^{k/2}\right)k^{k/2}.$

Consequently, $s_{k}^{\texttt{HC}}(n)\leq 1.64\sqrt{k}$, for $k$ sufficiently
large.

  * (ii)

If $n\leq 2^{k}$, then there exists a Hamiltonian cycle $H$ such that

$S_{k}(H)\leq\left(200+2.01^{k/2}\right)k^{k/2}.$

Consequently, $s_{k}^{\texttt{HC}}(n)\leq 1.42\sqrt{k}$, for $k$ sufficiently
large.

###### Proof.

Let $X\subseteq[0,1]^{k}$ be a point set of size $n$. We run Algorithm 1 from
Section 3.2. Let $F_{i}$ be the collection of paths at the $i$-th step, let
$e_{i}$ be the edge added in the $i$-th step, and let $F=F_{n-1}$ be the final
Hamiltonian path.

(i) We know that $|e_{i}|\leq\sqrt{\frac{2}{3}k}$ for $i\leq n-2$. Note that
$|e_{n-1}|\leq\sqrt{k}$ trivially. Now, let $f=ab$ be the edge where $a$ and
$b$ are the two endpoints of the final path $F$. Set $H=F+f$ to be the
Hamiltonian cycle when $f$ is added to $F$. Since $|f|\leq\sqrt{k}$ trivially,
we get

$\displaystyle S_{k}(H)$ $\displaystyle=\sum_{e\in
H}|e|^{k}=|f|^{k}+|e_{n-1}|^{k}+\sum_{i=1}^{n-2}|e_{i}|^{k}\leq
2\left(\sqrt{k}\right)^{k}+(n-2)\left(\sqrt{\frac{2}{3}k}\right)^{k}$
$\displaystyle\leq\left(2+2^{k}\cdot\left(\frac{2}{3}\right)^{k/2}\right)\cdot
k^{k/2}=\left(2+\left(\frac{8}{3}\right)^{k/2}\right)k^{k/2}.$

Consequently, $s_{k}^{\texttt{HC}}(n)\leq s_{k}(H)\leq 1.64\sqrt{k}$, for $k$
sufficiently large.

(ii) We classify the edges $e\in F$ into two types.

  1. 1.

_short_ edges: $|e|^{2}\leq\frac{100k}{199}$.

  2. 2.

_long_ edges: $\frac{100k}{199}<|e|^{2}$.

The number of short edges $e\in F$ is at most $n\leq 2^{k}$, trivially. The
number of long edges $e\in F$ is at most $199$ by Lemma 3.3 applied with
$m=200$. Now, let $f=ab$ be the edge where $a$ and $b$ are the two endpoints
of the final path $F$. Set $H=F+f$ to be the Hamiltonian cycle when $f$ is
added to $F$. Since $|f|\leq\sqrt{k}$ trivially, we get

$\displaystyle S_{k}(H)$
$\displaystyle\leq\left(200+2^{k}\cdot\left(\frac{100}{199}\right)^{k/2}\right)\cdot
k^{k/2}\leq\left(200+2.01^{k/2}\right)k^{k/2}.$

Consequently, $s_{k}^{\texttt{HC}}(n)\leq s_{k}(H)\leq 1.42\sqrt{k}$, for $k$
sufficiently large. ∎