April 2003
This was inspired by a result due to the Japanese mathematician Kakutani, and strengthened by Ralph Gomory (former head of IBM Research).
L=9.
An equilateral triangle inscribed in the circle, with vertices (1,0), (-1/2,sqrt(3)/2), (-1/2,-sqrt(3)/2) has three edges of length sqrt(3), so the cost of each link is 3, and the cost of any tour is 9.
U=16.
Gomory proved that the similar problem, with a unit square instead of a unit disk, has L=U=4. Inscribe the unit disk in a square of side 2; costs quadruple when distances double, so the larger square has U=16, and the same upper bound holds for the disk.
Gomory's proof:
Let AC be the hypotenuse of a right triangle ABC.
Lemma: given N nodes in ABC, there is a path starting at A, passing through each of the N nodes exactly once, and ending at C, whose cost is at most the square of the length (AC).(We will denote that as (AC)**2.)
Proof: Construct BD perpendicular to AC with D on side AC. BD partitions ABC into two smaller right triangles. Suppose N1 nodes are in triangle ABD and the remaining N2=N-N1 points are in triangle BCD. By induction, construct a path starting at A, passing through the N1 nodes, ending at B, with cost at most (AB)**2; and another path starting at B, passing through the N2 nodes, and ending at C, with cost at most (BC)**2. Pasting the two paths together we get a path starting at A, passing through the N nodes along with B, and ending at C, whose cost is at most (AB)**2+(BC)**2=(AC)**2. It's illegal because it uses the extra node B. But if E is the last node visited before B, and F is the next one visited after B, then angle EBF is acute or right, so that (EF)**2 is at most (EB)**2+(BF)**2, and replacing the two links (EB) and (BF) by the link (EF) we obtain a path whose cost is no worse, and which is legal (starts from A, passes through only the N nodes and not B, and ends at C). Start the induction with N=1, and observe that for a single interior node X, angle AXC is obtuse or right, so (AX)**2+(XC)**2 is at most (AC)**2.
Theorem: For the square of side 2, we have U=16.
Proof: Label the corners of the square ABCD in clockwise order. Given a constellation, temporarily append two nodes A,C at opposite corners of the square. We can construct a path from A to C visiting all nodes in triangle ABC, with cost at most (AC)**2=8, and another from C to A visiting all the other nodes (which are in triangle CDA) with cost at most 8. Concatenate the paths, and remove the spurious nodes A and C just as we did before, to obtain the desired Hamiltonian tour on the original N nodes with cost at most 16.
The lower bound L=16 is obtained from the four corners of the square. Of course these corners are not in the disk, so the lower bound L=16 does not hold for the disk. So our lower and upper bounds for the disk don't match (L=9, U=16); we're hoping a clever reader can do better than that.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com