# What if the travelling salesman travelled by plane?

It seems intuitive to solve a 2D dot-to-dot travelling salesman problem by eye using a greedy strategy. However we can only solve the TSP by eye if the graph is topographically accurate e.g. if A to B is 10 and A to C is 10 then B to C can't be 1000.

Is the greedy strategy still sub-optimal when we obey 2D scaling, ie travelling by plane? Below I managed to create a topographically accurate example where the greedy strategy is indeed sub optimal:

Starting at S:

• Greedy: S B C A S => 2.83 + 4 + 5 + 2.2 => 14.03
• Optimal: S A B C S => 2.2 + 3 + 4 + 3.16 => 12.36

Is there something special about the example above that will be common to all suboptimal greedy routes? Can geometry be used to minimize error?

• What is your greedy strategy exactly? It seems your greedy path does not follow the immediate lowest cost edge.. – Curious_Dim Jan 26 '18 at 0:07
• I don't understand your question. Nothing in the definition of the TSP alters in any way if you change the mode of transport. There's still a cost of travelling between any two cities and you're still trying to minimize the overall cost. – David Richerby Jan 26 '18 at 0:21
• What 'geometry' gets you is the triangle inequality. Approximation algorithms for TSP use this, and without that assumption TSP becomes significantly harder to approximate. – orlp Jan 26 '18 at 0:22
• What I guess david is trying to do is to convert costs into lengths on paper, and then try to solve TSP by just inspecting the edges with the eyes. But if this is the case costs may not end to be proportionally right like your SB edge which is less in length than SA edge but still has greater cost – Curious_Dim Jan 26 '18 at 0:50
• Did you mean to ask about planar TSP, rather than traveling by plane? ​ ​ – user12859 Jan 26 '18 at 1:18