3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Your problem is very close to TSP on the plane with the L1 metric. For this problem, there is a PTAS due to Arora, while the problem itself is probably NP-hard. Practically speaking, if your goal were indeed TSP rather than its "Hamiltonian path" variant, you could apply any approximation algorithm that works for metric TSP.

$\endgroup$
  • $\begingroup$ Thank you for your answer. This solution works only for TSP, and will not work for TSPP. It's title states it is Euclidian, but there is note, "with almost no modification, when distance is measured using any geometric norm", which is also disturbing, as no modification are explained. $\endgroup$ – Evil Sep 4 '15 at 11:57
3
$\begingroup$

It turns out that it is indeed the Traveling Salesman Path Problem (TSPP). There are well suited approximation algorithms:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.