From: David Eppstein Subject: Re: Random Hamiltonian Cycles in a Fixed Area Date: Fri, 02 Nov 2001 08:39:23 -0800 Newsgroups: sci.math Summary: Length of Traveling Salesman path for large graphs in small area In article <9rtkgb$337$1@coward.ks.cc.utah.edu>, "Chris Piantes" wrote: > Basically, I face the problem of finding the longest Hamiltonian cycle of a > graph of random points in a fixed area. As an amateur mathematician I > thought of somehow spreading the points on the graph evenly throughout the > area and splitting it into equilateral triangles, one for each point (or > constituent,) finding the length of the side of the triangle and multiplying > it by the number of points in the graph. I came up with > > Length = k * Sqrt(Area * Population) > > where k is a proportionality constant (I got k > 3/2). You also need some assumption that the area is not too thin. But with that, you can get rid of the assumption of randomness -- it is known that, e.g., no matter how you distribute n points in a square, the length of the TSP will be O(sqrt(area * n)). One proof idea is to use a space-filling curve such as the Peano curve to get within distance sqrt(area/pop) of every point in the square, then detour from the curve to each point of the population. The length is optimized when the space-filling curve length balances the detour lengths. I have a paper on some related problems, , which you can check for further references. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/