15-3 Bitonic euclidean

In the euclidean traveling-salesman problem, we are given a set of $n$ points in the plane, and we wish to find the shortest closed tour that connects all n points. Figure 15.11(a) shows the solution to a $7$ -point problem. The general problem is NP-hard, and its solution is therefore believed to require more than polynomial time (see Chapter 34).

J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly rightward to the rightmost point, and then go strictly leftward back to the starting point. Figure 15.11(b) shows the shortest bitonic tour of the same $7$ points. In this case, a polynomial-time algorithm is possible.

Describe an $O(n^2)$ -time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same $x$ -coordinate and that all operations on real numbers take unit time. ( $\textit{Hint:}$ Scan left to right, maintaining optimal possibilities for the two parts of the tour.)

First sort all the points based on their $x$ coordinate. To index our subproblem, we will give the rightmost point for both the path going to the left and the path going to the right. Then, we have that the desired result will be the subproblem indexed by $v$ , where $v$ is the rightmost point.

Suppose by symmetry that we are further along on the left-going path, that the leftmost path is going to the $i$ th one and the right going path is going until the $j$ th one. Then, if we have that $i > j + 1$ , then we have that the cost must be the distance from the $i − 1$ st point to the ith plus the solution to the subproblem obtained where we replace $i$ with $i − 1$ . There can be at most $O(n^2)$ of these subproblem, but solving them only requires considering a constant number of cases. The other possibility for a subproblem is that $j \le i \le j + 1$ . In this case, we consider for every $k$ from $1$ to $j$ the subproblem where we replace $i$ with $k$ plus the cost from $k$ th point to the $i$ th point and take the minimum over all of them. This case requires considering $O(n)$ things, but there are only $O(n)$ such cases. So, the final runtime is $O(n^2)$ .