I have two sets $X$ and $Y$ of 2-dimensional points. The points are floating point numbers. The objective is to sort them in such way that sum of differences in distances of consecutive sorted points is minimal.I tried to solve this problem by localisation (dividing the plane by smaller grids of sorted points) and then connecting clusters - but this is a greedy and an approximate approach - the problem here is in setting grid size, but this is not guaranteed to give any bounds on how optimal the solution is, and it is rather time consuming (without a well-defined objective function).Another attempt was to sort them by the x-coordinate, then find the minimum. But this approach fails. Normal sorting by two coordinates fails and is highly unstable.The problem resembles the TSP problem, but the path is not closed and metric used is L1 (Manhattan, TaxiCab).The solution I am looking for will probably be approximate. Finding the minimal and the second minimal distance from every point and connecting them gives good but for sure not minimal sum.The problem I am having is with giving the objective function.
Minimising sum of consecutive points distances Manhattan metric
algorithms;optimization;sorting;approximation
It turns out that it is indeed the Traveling Salesman PathProblem (TSPP). There are well suited approximation algorithms:  The An-Kleinberg-Shmoys Algorithm for the Traveling Salesman Path Problem Analysis of Christofides' heuristic: Some paths are more difficult than cycles And the fresh: Reassembling Trees for the Traveling Salesman by Jens Vygen