On Fréchet Traveling Salesmen Problems

Assume by contradiction that all the neighbors of a vertex $v$ in $\mathrm{MST}(S)$ are far from $v$. By Lemma 2, $v$ has a neighbor $u$ in $G_{{\epsilon }^{\ast }}$, and therefore $u$ is close to $v$. This contradicts the fact that the MST contains a nearest neighbor for each vertex (by Kruskal’s algorithm). $◀$

We now show how to construct two curves $P$ and $Q$ that partition $S$ by traversing $\mathrm{MST}(S)$ in a DFS order, starting from a leaf vertex of $\mathrm{MST}(S)$ as a root, and coloring the vertices red and blue. The blue vertices will be in $P$, and the red vertices in $Q$. The order of the points along the curves would be the same order in which they where colored during the algorithm.

Consider a vertex $v$ in the rooted tree $\mathrm{MST}(S)$. Let $I_{\text{close}}(v)$ be the set of children of $v$ that are close to $v$, and similarly, $I_{\text{far}}(v)$ will be the set of children of $v$ that are far from $v$. In addition, let $L(v)=\{u\mid u\in I_{\text{close}}(v),I_{\text{close}}(u)=\mathrm{\varnothing }\}$. In other words, $L(v)$ is the set of lonely children of $v$ – those that are either leaves in $\mathrm{MST}(S)$, or that do not have close children – and therefore must be in $v$’s star. Notice that by Observation 9, all the nodes in $L(v)$ are close to $v$.

Let $v$ be the current vertex visited by the DFS algorithm. The invariant of our recursive DFS algorithm is that if $L(v)$ is empty, then there must be at least one vertex in $I_{\text{close}}(v)$. The algorithm has two main steps: in the first step we color vertices in red and blue, and the second step contains the recursive calls.

In this step, we color the entire star that $v$ belongs to using Algorithm 1. Note that $v$ can be either a center or a leaf in that star. Also, Algorithm 1 colors exactly one vertex in blue and the rest in red. We progress in recursion on the vertices of the tree. In each recursive call, we activate the coloring algorithm on newly colored vertices in the following order:

1. 1.

   First, activate the algorithm on children of vertices that are colored red, in reversed order (last colored first called).

2. 2.

   then, activate the algorithm on children of the blue vertex.

First, notice that when the algorithm is called with a vertex $v$ in a recursive step, then $v$ and its entire subtree were not colored yet. Moreover, we show that the following invariant holds in each step of the algorithm.

Assume by contradiction that in some step of the algorithm both $L(v)$ and $I_{\text{close}}(v)$ are empty. Then, by Observation 9, $v$ must have a parent $t$ in $\mathrm{MST}(S)$ such that $v\in I_{\text{close}}(t)$, and $t$ was already colored by the algorithm. Moreover, $v$ is in $L(t)$, because $I_{\text{close}}(v)=\mathrm{\varnothing }$. Therefore, it is not possible that $t$ was colored blue, because then $v$ would have been already colored red and would not be called recursively. In addition, $t$ is not a lonely child of its parent, because $I_{\text{close}}(t)\ne \mathrm{\varnothing }$. Therefore, if $t$ was colored red, then it must be in step 2(a) of the algorithm, which means that $L(t)$ is empty, but this is not possible because $v\in L(t)$. $\mathrm{⊲}$

Let $P=\{p_1,\mathrm{\dots }{p}_k\}$ (resp. $Q=\{q_1,\mathrm{\dots }{q}_m\}$) be the set of vertices that were colored blue (resp. red), in the order in which they were colored during the DFS scan.

Calculating the Euclidean MST for the set $S$ takes $O(n\log n)$ time. A standard DFS traversal over the MST also requires $O(n)$ time. The additional overhead in the algorithm comes from recursively scanning the $L(v)$ children of each vertex $v$. Since $|L(v)|\le 5$ in the EMST, this adds at most $O(n)$ additional operations. Thus, the total running time remains $O(n\log n)$. $\mathrm{⊲}$

We show that in each step of the algorithm, we color a star in $\mathrm{MST}(S)$ with edges of length at most ${\epsilon }^{\ast }$. The center is colored blue, and the leaves red. Let $v$ be the current vertex. There are two cases:

• $\mathrm{■}$

  If $L(v)$ is not empty, then $v$ is colored blue and the nodes in $L(v)$ are colored red. Since $L(v)\subseteq I_{\text{close}}(v)$ (by Observation 9), this red-blue star has edges of length at most ${\epsilon }^{\ast }$.

• $\mathrm{■}$

  If $L(v)=\mathrm{\varnothing }$, then the algorithm picks a vertex $u\in I_{\text{close}}(v)$ and color it blue. This vertex becomes the center of a star with its children $v\cup L(u)$ which are colored red. Since $L(v)\subseteq I_{\text{close}}(u)$, we again obtain a red-blue star with edges of length at most ${\epsilon }^{\ast }$.

Since the vertices of $P$ and $Q$ are ordered by the time they were colored, we get that the sequence of starts corresponds to a paired-walk of cost at most ${\epsilon }^{\ast }$ between $P$ and $Q$, as required. $\mathrm{⊲}$

Next, we bound the lengths of the curves $P$ and $Q$ in relation to $\mathrm{MST}(S)$. Notice that the order in which we color the blue vertices (the vertices of $P$) follows a classic DFS preordering, and therefore we clearly have $\mathrm{\ell }(P)\le 2\cdot \mathrm{\ell }(\mathrm{MST}(S))$. However, the order in which we color the red vertices slightly differs from a classic DFS preordering. However, since all the children of $v$ that are colored in this step are close to $v$, the additional traversal overhead is small. The following claim together with Claim 12 implies Theorem 8.

Let $T$ be the path on all the points in $S$, which is obtained by traversing the edges of $\mathrm{MST}(S)$ in the order in which the algorithm colors the vertices, regardless of their color. Clearly $\mathrm{\ell }(T)\ge \max \{\mathrm{\ell }(P),\mathrm{\ell }(Q)\}$. We show that $\mathrm{\ell }(T)\le 2.75\cdot \mathrm{\ell }(\mathrm{MST}(S))$.

Recall that the degree of any vertex in $\mathrm{MST}(S)$ is at most $5$. Since we choose the root of $\mathrm{MST}(S)$ to be a leaf, then for every vertex $v$ in the rooted tree, $L(v)$ may contain at most $4$ vertices. Consider a step of the algorithm were the current vertex is $v$. If $v$ was colored blue, denote $L(v)=u_1,\mathrm{\dots },u_k$ for $1\le k\le 4$. Then, the subpath of $T$ that was added in this step is $T_v=\{v,u_1,v,u_2,v,\mathrm{\dots },u_k\}$. This is because, in $T$, we are moving from $u_i$ to $u_{i+1}$ through $v$, since $\{u_i,u_{i+1}\}$ is not an edge in $\mathrm{MST}(S)$. If $v$ was colored red, the algorithm picked a vertex $u\in I_{close}(v)$. Denote $L(u)=u_1,\mathrm{\dots },u_k$ for $1\le k\le 4$. The subpath of $T$ that was added in this step is $T_v=\{v,u,u_1,u,u_2,u,\mathrm{\dots },u_k\}$.

We show how to charge the edges of $\mathrm{MST}(S)$ for each such star-subpath and for each of the edges that are connecting between star-subpaths. First, notice that in each star-subpath $T_v$, each edge of the star is traversed at most twice. Let $U={\cup }_{x\in P}{T}_x$ be the set of edges that are charged for the star-subpaths themselves. Because the edges of the stars are disjoint, each edge in $U$ is charged at most twice.

Let $W$ be the set of edges that are traversed in $T$ when connecting between any two star-subpaths. Each edge of $W$ is charged at most twice because we traverse the stars following the classic DFS order. Therefore, in both sets $U,W$ each edge is charged at most twice. Notice that $U,W$ are distinct.

The edges in $U$ have length at most ${\epsilon }^{\ast }$, so edges of length larger than ${\epsilon }^{\ast }$ can only appear in $W$. In addition, edges that are incident to leaves in $\mathrm{MST}(S)$ appear only in $U$, because they do not connect between star-subpaths. We conclude that leaf-edges are charged only twice, and edges of length larger than ${\epsilon }^{\ast }$ are also charged only twice.

Consider an edge $\{v,u\}\in T_v$ such that $L(v)$ is empty and $u\in I_{close}(v)$. Notice that the edge $\{v,u\}$ is charged only once in $U$ (it appears once in $T_v$) and once in $W$ (to connect $u$ with the centers of stars in $v$’s subtree), so in total it is charged at most twice.

The only case left to handle is edges $\{x,u_i\}$ in a star such that $u_i\in L(x)$ ($x$ can be either the current vertex or its child $u\in I_{\text{close}}(v)$). In this case, $I_{close}(u_i)=\mathrm{\varnothing }$. If $u_i$ is not a leaf, then there exists an edge $\{u_i,w_i\}$ such that $w_i\in I_{far}(u_i)$. Since the algorithm recursively runs on $w_i$, the edges $\{u_i,w_i\}$ is in $W$. In other words, for every $\{x,u_i\}\in U$ there exists an edge $\{u_i,w_i\}\in W\setminus U$ such that $\Vert u_i-w_i\Vert >{\epsilon }^{\ast }$, which is charged only twice. Therefore, if $\{x,u_i\}$ is charged four times (twice in $U$ and twice in $W$), we charge it three times, and transfer the forth charge to $\{u_i,w_i\}$, so that both edges are charged only three times in total. Note that no other edge can transfer its charge to $\{u_i,w_i\}$, because $w_i$ has to come after $u_i$ in the order of the traversal.

This gives a bound of $3\cdot \mathrm{\ell }(\mathrm{MST}(S))$. To further improve the bound, notice that the last edge $\{x,u_k\}$ is charged only once in $U$. Moreover, it is also charged only once in $W$, because the children in its subtree are the first to be called recursively in this step, so $\{x,u_k\}$ only appears on the subpath that goes back to $x$. In the worst case, when $k=4$, we charge the first three edges $\{x,u_1\},\{x,u_2\},\{x,u_3\}$ a total of $3$ times (by transferring one charge to the corresponding edge in $W$), and $\{x,u_4\}$ is charged only twice. By choosing the farthest child to be colored last, i.e., $\Vert x-u_4\Vert \ge \max \{\Vert x-u_1\Vert ,\Vert x-u_2\Vert ,\Vert x-u_3\Vert \}$, each of the first three edges can transfer a charge of $\frac{1}{4}$ to $\{x,u_4\}$, resulting in a total charge of at most $2⁤\frac{3}{4}$ per edge of $\mathrm{MST}(S)$, as claimed. $\mathrm{⊲}$ Theorem 8 follows from Claim 11, Claim 12, and Claim 13.

Let $P$ and $Q$ be the curves obtained by the algorithm in the previous section. Then by Theorem 8 $\mathrm{\ell }(Q)\le 2.75\cdot \mathrm{\ell }(\mathrm{MST}(S))$. For $P$, note that it follows a DFS traversal of the $\mathrm{MST}(S)$ restricted to the centers. Since each edge is used at most twice and no vertex is repeated as in $Q$, this gives $\mathrm{\ell }(P)\le 2\cdot \mathrm{\ell }(\mathrm{MST}(S))$. Combining the two bounds yields $\mathrm{\ell }(P)+\mathrm{\ell }(Q)\le 4.75\cdot \mathrm{\ell }(\mathrm{MST}(S))$. $◀$ This result can be improved by using a $(1+\epsilon )$ approximation for TSP (for $\epsilon >0$) on one of the curves. We make use of the algorithm of Kisfaludi-Bak, Nederlof and Węgrzycki [20] which computes in $2^{O({\epsilon }^{1-d})}n\log n$ time. We get the following result.

Given the set of stars $S_1,\mathrm{\dots },S_k$ that were obtained in the proof of Lemma 2, each star $S_i$ has a blue vertex that is connected in $S_i$ to a set of red vertices. We run an algorithm that computes a $(1+\epsilon )$ approximation for the TSP. On the blue vertices, and obtain a curve $P$ with the length $(1+\epsilon )\cdot \mathrm{\ell }(\mathrm{TSP}(S))$.

We then construct the curve $Q$ on the red vertices following the order of the blue vertices in $P$, i.e., for each vertex $v\in P$ that corresponds to the star $S_i$, we connect the red vertices of $S_i$, and then connect these red paths according to the TSP order on the blue vertices. We can bound the length of $Q$ by the length of a curve traversing $P$ with detours for traversing the red vertices. The sum of lengths of these detours is bounded by traversing each edge of a star twice, which is bounded by $2\cdot \mathrm{\ell }(\mathrm{MST}(S))$. We therefore get that $\mathrm{\ell }(Q)\le \mathrm{\ell }(P)+2\cdot \mathrm{\ell }(\mathrm{TSP}(S))$ and thus $\mathrm{\ell }(Q)+\mathrm{\ell }(P)\le (4+\epsilon )\cdot \mathrm{\ell }(\mathrm{TSP}(S))$. $◀$

By concatenating $P$ and $Q$, we obtain a path of at most $\mathrm{\ell }(P)+\mathrm{\ell }(Q)+\epsilon$ that traverses all the points of $S$, which is a feasible solution for TSP on $S$. $◀$Denote by $P^{\ast },Q^{\ast }$ two curves that partition $S$ with ${\text{d}}_{dF}(P^{\ast },Q^{\ast })={\epsilon }^{\ast }$ such that $\max \{\mathrm{\ell }(P^{\ast }),\mathrm{\ell }(Q^{\ast })\}$ is minimized.

Assume by contradiction that ${\epsilon }^{\ast }>L$. That means that all edges of both $P$ and $Q$ are of strictly smaller length than ${\epsilon }^{\ast }$. Denote $P=\{p_1,\mathrm{\dots },p_k\}$ and $Q=\{q_1,\mathrm{\dots },q_m\}$. If $k\ge 2$, then the discrete Fréchet distance between $P_{\text{odd}}=\{p_1,p_3,p_5,\mathrm{\dots }\}$ and $P_{\text{even}}=\{p_2,p_4,p_6,\mathrm{\dots }\}$ is at most $L$. Similarly, if $m\ge 2$, then the Fréchet distance between $Q_{\text{odd}}=\{q_1,q_3,q_5,\mathrm{\dots }\}$ and $Q_{\text{even}}=\{q_2,q_4,q_6,\mathrm{\dots }\}$ is at most $L$. Therefore, the discrete Fréchet distance between $P_{\text{odd}}\circ Q_{\text{odd}}$ and $P_{\text{even}}\circ Q_{\text{even}}$ is at most $L$, in contraction to the optimality of ${\epsilon }^{\ast }$. $◀$

Note that if one of $P,Q$ is a single vertex, the above lemma may not be correct. Let $S=\{p,q_1,q_2,\mathrm{\dots }\}$ such that $\Vert p-q_i\Vert =\epsilon$ for some $\epsilon >0$. Let $\Vert q_i-q_j\Vert \ll \epsilon$ for all $q_i,q_j\in Q$. Then $\epsilon$ is the optimal Fréchet distance. And yet, the lemma does not hold for $P=\{p\}$ and $Q=\{q_1,q_2,\mathrm{\dots }\}$.

An immediate corollary of Observation 16 and Lemma 17 is that $\mathrm{\ell }(\mathrm{TSP}(S))\le \mathrm{\ell }(P)+\mathrm{\ell }(Q)+\epsilon \le 3\cdot \max \{\mathrm{\ell }(P),\mathrm{\ell }(Q)\}$, and $\mathrm{\ell }(\mathrm{TSP}(S))\le 2\cdot (\mathrm{\ell }(P)+\mathrm{\ell }(Q))$. Therefore, by Theorem 8 we have the follwiing corrolary.

Consider the set of stars $S_1,\mathrm{\dots },S_k$ that were obtained in the proof of Lemma 2. If the degree of each star is at most two (i.e. $|\text{red}(S_i)|\le 2$ for every $1\le i\le k$), then by applying arguments similar to the proof of Theorem 19, we get that $\max \{|P|,|Q|\}=\lceil n/2\rceil$ as required.

Otherwise, let $S_i$ be a star such that $|\text{red}(S_i)|\ge 3$. Let $c=\text{blue}(S_i)$, then there is at least one pair of nodes $u,v\in \text{red}(S_i)$ such that the smaller angle $\mathrm{\angle }ucv$ at at most $\frac{2\pi }{3}$. Thus, by the law of cosines, the distance between them is

Since the length of any edge in $S_i$ is at most ${\epsilon }^{\ast }$, we have

We now split $S_i$ into two stars: remove $v,u$ from $\text{red}(S_i)$ and create a new star, $S_{k+1}$, with $\text{red}(S_{k+1})=\{v\}$ and $\text{blue}(S_{k+1})=u$.

We continue this process until all our stars have degree at most two. Notice that any star that we add consists of a single pair of points with distance at most $\sqrt{3}\cdot {\epsilon }^{\ast }$. Therefore, when applying the arguments from the proof of Theorem 19 as before, we obtain $\max \{|P|,|Q|\}=\lceil n/2\rceil$, and ${\text{d}}_{dF}(P,Q)\le \sqrt{3}\cdot {\epsilon }^{\ast }$. $◀$

The example in Figure 6 shows that the bounds in Theorem 19 and Theorem 21 are tight, as we conclude in the observation below.