Xavier Holt edited Monotonicity_TSP_See_ref_fig__.md  almost 8 years ago

Commit id: 24b7a07a62a329d04832f61eedca94ef3eb7b29f

deletions | additions      

       

* Let \(p_{i-1}, p_{i+1}\) be the points before and after \(p\) in our travelling-salesperson cycle.  * Let \(a,b\) be \(d(p_{i+1}, p), d(p_{i+1}, p)\) respectively.  * Let \(c\) be \(d(p_{i+1}, p_{i-1})\).  * Let the segment of the cycle not involving anythree  of these three  points be defined \(L\). If we remove \(p\) from our pointset S, we can always join \(p_{i-1},p_{i+1}\). We don't have to prove that this decision results in the optimal TSP for the reduced pointset, just that we **1)** get a valid cycle and **2)** never do worse that \(|TSP(S')|\).