Xavier Holt edited Monotonicity_TSP_See_ref_fig__.md  almost 8 years ago

Commit id: d587046bf99c26b71708344b1a5b31e2e1b6260b

deletions | additions      

       

For all \(p\in S', \not\in S\):  * 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)\) \(|p_{i+1}, p|, |p_{i+1}, p|\)  respectively. * Let \(c\) be \(d(p_{i+1}, p_{i-1})\). \(|p_{i+1}, p_{i-1}|\).  * Let the segment of the cycle not involving any 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')|\).