最接近的一对点采用不同的方法

Question

我试图解决这个问题，我想出了一个解决方案，如下所示，这与“维基百科”算法完全不同。我无法理解我的解决方案有什么问题，这也是O（nlogn）。

输入：沿x-y轴的坐标集。 {（2,4），（5,3），（3,7），（4,2），（6,3）}

我的解决方案

1. 对给定的集合wrt x坐标进行排序。 {（2,4），（3,7），（4,2），（5,3），（6,3）}。复杂性O（nlog）
2. 找到min {连续对之间的距离}，我们称之为min_x。复杂度O（n）
3. 对给定的集合wrt y坐标进行排序。 {（4,2），（5,3），（6,3），（2,4），（3,7）}。复杂性O（nlog）
4. 找到min {连续对之间的距离}，让我们称之为min_y。复杂度O（n）
5. min_d = min（min_x，min_y）导致min_d的对是具有最短距离的对。

这是错的吗？我错过了什么？

Answer 1

是的，这是错的。考虑集合{（0,0），（0,10），（10,0），（0.2,0.2）}作为计数器示例。你的方法永远不会有（0,0）和（0.2,0.2）作为任何一个排序中的连续元素，因此永远不会被发现为彼此最接近的两个点。

Answer 2

您的算法将产生一个错误的最佳对，例如以下示例：

var points : [(Int,Int)] = [(0,0),(1,10),(10,1),(3,3)]

/* xmin solution: (1,10), (3,3) (dist = sqrt(4+49) = sqrt(53))
   from sorted list: (0,0),(1,10),(3,3),(10,1)                 */

/* ymin solution: (10,1), (3,3) (dist = sqrt(53))
   from sorted list: (0,0),(10,1),(3,3),(1,10)                 */

/* real solution: (0,0), (3,3) (dist = sqrt(18) < sqrt(53))    */

Answer 3

是的，这是错的。当x ^ 2或y ^ 2中的任何一个最小时，对于sqrt（x^2 + y^2）是最小的没有必要。

最着名的解决方案具有O（nlogn）的时间复杂度。可以在文本Here第33.4页第1039页中找到解决方案。

只需要第33.4节就不需要阅读整章了。