algorithm - 最近的一对点不同的方法

Question

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

输入:沿 x-y 轴的坐标集。 {(2,4),(5,3),(3,7),(4,2),(6,3)}

我的解决方案:

1. 根据 x 坐标对给定的集合进行排序。 {(2,4),(3,7),(4,2),(5,3),(6,3)} 。复杂度 O(nlog)
2. 找到最小{连续对之间的距离}，我们称之为 min_x。复杂度 O(n)
3. 根据 y 坐标对给定的集合进行排序。 {(4,2),(5,3),(6,3),(2,4),(3,7)} 。复杂度 O(nlog)
4. 找到最小{连续对之间的距离}，我们称之为 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) 作为任意顺序中的连续元素，因此永远不会被发现是彼此最接近的两个点。