Sorting points such that the minimal Euclidean distance between consecutive points would be maximized

Question

Given a set of points in a 3D Cartesian space, I am looking for an algorithm that will sort these points, such that the minimal Euclidean distance between two consecutive points would be maximized.

It would also be beneficial if the algorithm tends to maximize the average Euclidean distance between consecutive points.

Edit:

I've crossposted on https://cstheory.stackexchange.com/ and got a good answer. See https://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin.

Answer 1

Here is a lower bound for the cost of the solution, which might serve as a building block for branch and bound or a more unreliable incomplete search algorithm:

Sort the distances between the points and consider them in non-increasing order. Use http://en.wikipedia.org/wiki/Disjoint-set_data_structure to keep track of sets of points, merging two sets when connected by a link between two points. The length of the shortest distance you encounter up to the point when you merge all the points into one set is an upper bound to the minimum distance in a perfect solution, because a perfect solution also merges all the points into one. However your upper bound may be longer than the minimum distance for a perfect solution, because the links you are joining up will probably form a tree, not a path.

Answer 2

You can model your problem by graph, draw line between your points, now you have a complete graph, now your problem is finding longest path in this graph which is NP-Hard, see wiki for longest path.

In fact I answered a second part of problem, maximize average, which means maximize path which goes from every node of graph, if you weight them as 1/distance it will be a travelling salesman problem (minimize the path length) and is NP-Hard. and for this case may be is useful to see Metric TSP approximation.