That Hilbert Curve solution is really handy to know about. If you were writing a game where the player competes with an AI at traveling salesman (Pacman without

That Hilbert Curve solution is really handy to know about. If you were writing a game where the player competes with an AI at traveling salesman (Pacman without the ghosts race), a fast 75% optimal algorithm sounds perfect. I think you can do the Hilbert Curve in n log n time by loading all the cities into a quad tree and traversing it in a Hilberty order. Is that the fastest way?