Convex hulls, the TSP, and long drives


The ‘God Plays Dice’ blog here makes me aware of a really fascinating little project: in 1998, apparently, Barry Stiefel decided to use a week off work to see the United States. All of them. And by dint of driving with a ruthlessness I can hardly believe, he managed it, albeit with some states just barely peeked at from the road, with Kentucky surprisingly hard to get at. Stiefel also managed, in a 2003 road expedition, to visit 21 states in a single carefully chosen day. I’m impressed.

This all seems connected to the Travelling Salesman Problem, or generally the problem of how to find the beset way to do something when there are so many ways to do it there’s no hope of testing all the possible combinations, but when there aren’t an infinite continuum of ways so that you can’t use calculus techniques to find a solution. Problems like this tend to be interesting ones: you can usually see exactly why the problem might be interesting, and you can work out a couple easy little toy cases, and if you fiddle around with toys that are a little more realistic you see just how hard they are.

I’ve never driven in more than six United States states in a day, near as I can tell. I have driven across Pennsylvania, even though that means crossing the Appalachians, and as anyone from the East Coast knows deep down, the Appalachians are a fundamentally uncrossable geographic barrier and anyone claiming to have crossed it is surely mad.

God plays dice

I’ve been reading the book In Pursuit of the Traveling Salesman by William Cook lately. In Chapter 10, on “The Human Touch”, Cook mentions a paper, by James MacGregor and Thomas Ormerod, “Human performance on the traveling salesman problem”. One thing that this paper mentions is that humans reach solutions to the TSP by looking at global properties such as the convex hull — there’s a theorem that a tour must visit the vertices of the convex hull in order.

This reminds me of one of my favorite travelogues, Barry Stiefel’s fifty states in a week’s vacation, in which Stiefel visited all fifty states on a week’s vacation (doing the lower 48 by driving, and flying to Alaska and Hawaii) Stiefel writes, in regard to getting to Kentucky: Now things were going to get complicated. Until then, my route had been primarily one of following the inside perimeter…

View original post 147 more words

Advertisements