Convex hulls, the TSP, and long drives

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 of the states on the outside perimeter of the 48 states. When planning the route, I had stared at the map for over an hour before concluding that Kentucky was going to be the toughest state to get. I just couldn’t plan a route that efficiently went through it. So I had to do a several-hour out-and-back loop to get it.

It’s not obvious that Kentucky would be so hard. Kentucky borders Virginia and Ohio, both of which are on that outside perimeter, while a bunch of states further west don’t border any of the perimeter states. (By my eyeballing, those are Kansas, Nebraska, and Missouri.) Stiefel chose to approach Kentucky from the southeast, though, and southeastern Kentucky is not exactly crawling with highways. And as you might gather from the title of Stiefel’s page, he was in search of a shortest-time route, not a shortest-distance one.