Geometric Approximation I

5.1. Back to complexity:

NP-completeness, PTAS, LTAS.

5.2. The Traveling Salesman's Problem (TSP):

hardness of approximation, metric TSP, Euclidean (planar) TSP.

-- TD:

curve reconstruction using Christofides' $\frac{3}{2}$-approximation of metric TSP (code for perfect matching + eulerian tour provided?).