排序点，使得连续的点之间的最小欧几里德距离将被最大化 [英] Sorting points such that the minimal Euclidean distance between consecutive points would be maximized

问题描述

鉴于三维直角坐标空间中的点的集合，我在寻找一种算法，将这些点进行排序，使得最小欧几里德连续两点之间的距离将被最大化。

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.

编辑：

我crossposted在 http://cstheory.stackexchange.com/ 并得到了很好的答案。请参阅<一href="http://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin">http://cstheory.stackexchange.com/questions/8609/sorting-points-such-that-the-minimal-euclidean-distance-between-consecutive-poin.

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

推荐答案

下面是该解决方案的成本，它可以作为一个构建块分支定界或更不可靠的不完全搜索算法的下限：

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:

排序点之间的距离，并考虑它们在非增序。使用 http://en.wikipedia.org/wiki/Disjoint-set_data_structure 跟踪的点的集合，两点之间连接由一个链接时合并两个集。你遇到最多的问题，当你合并所有的点为一组的最短距离的长度是一个上限，以一个完美的解决方案的最小距离，因为一个完美的解决方案还融合了所有的点为一体。但是您上限可能比一个完美的解决方案的最小距离更长，因为要加入了链接可能会形成一棵树，而不是一个路径。

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.

这篇关于排序点，使得连续的点之间的最小欧几里德距离将被最大化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！