Find closest pair points in 2D plane. Divide and conquer

思路大概很简单,divide的步骤就是 按 x轴坐标 不断的把所有的点分成两部分。比如原集合S, 分成了左边S1和右边S2.

那么假设 let d = Math.min(rec(S1), rec(S2));这里rec(S1)代表所有S1里面的点的最小距离。rec(S2)代表所有S2里面的点的最小距离。

那么rec(S) = Math.min(d, cross(S1,S2)), cross(S1,S2) 代表一个点在S1, 一个点在S2.

这里要注意一点就是,我一开始以为是把最中间的两个点的中点垂直画一条线(为了避免这条直线经过某个点), 后来发现这样不对, 因为比方说5个 点,第三个点恰好就在中间,那怎么办? 所以根据stanford那个视频呢, 我们以其中一个点的x坐标为分界线。比如如果有5个点, 那么第三个点作为分界线L,其中p1, p2 分到左边, p3, p4,p5 分到右边。 也就是左边是开区间, 右边是闭区间。 所以如果6个点的话,就第四个点为分界线, 两边个3个点。

接着呢就以L 左右-d, +d 的区间内找一对点,看距离能不能比d小。

这里呢如果用暴力法,肯定n方了, 那就没啥意义。

所以精华就在 有个线性的解法。首先我们需要把这个区间里面所有的点按照y 排序。但是我们不能直接排, 直接排序的话复杂度就高了, 所以我们这样做, 一开始就按y排一次序。 这样的话 我们每次只要按照这个y排序的顺序扫描所有点, 然后 根据x的界限筛选point, 就得到了这样的一个排序好的point的集合。这么做的复杂度是n而不是nlogn。

这里我们有个结论, 对于任意一个这样的点Px呢, 我们只需要按照y的值向上找到最近的7个比Px的y坐标大的点,并让他们一一和Px比较。所有的可能和Px的距离小与d的点必然就在这7个点之中了(也可能不存在, 但最多就找七次就好了)。下面证明一下,

我们以经过Px与Y轴垂直的直线,以及L 左右两边距离为d的虚线为边界画一个矩形。长为2d,宽为1d, 然后再把这个矩形切成d/2的 正方形。因为S1, S2 各自内的点的距离最小为d, 所以 每个正方形里面最多只能放一个点(正方形的对角线距离最大也就1/Math.sqrt(2) < 1,放两个的话,距离必然比d小了). 因为我们只关注L 左右距离为d的点, 所以矩形左右外的点不考虑, 上面也不用考虑,因为距离肯定大于d.(我们要尝试找小于d的pair) , 为啥不向Px下面的点考虑呢? 因为当我们遍历到下面的点的时候, 从他们的上面的七个点遍历就包含了这种情况。也就是为了避免重复。

简而言之,对于任何的点Px, 如果存在距离小于d, 那么他一定在这个矩形里面, 而且这个矩形最多含有7个其他的点(有可能实际只有2个,3个或者0个)。而且他们的y 大于或者等于Px的y。所以我们每次循环比较比Px的y大于或者等于的按y排序的最近的7个点必定cover了距离小于d的case。 所以这一步复杂度是线性的。(自己可以体会一下如果发现多余7个点的y和 Px的y相同的情况可不可能)

因此得证!

题外话啊,我这道题我看了很多种说法,有人说找7个点, 有的说12个点, 有的说6个点。 这里呢据说6个点就足够了, 但是证明很复杂, 所以呢 我们就找7个点, 反正复杂度一样。

最后附上一个 Stanford的视频讲解, 目前看到讲的最清楚的

https://www.youtube.com/watch?v=P7erYilqF6o

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.