平面最近点对问题

Contents
  1. 1. 问题简述
  2. 2. 暴力求解
  3. 3. 分治法
  4. 4. 分治法实现

问题简述

$给定二维平面上N个点,定义距离为欧氏距离$
$对于N个点组成的所有点对(i, j),i\ne j, i, j\in[1,N]$
$求最小的(i,j)点对距离$

暴力求解

  • 显然暴力求解的时间复杂度是$O(n^2)$的,是否可以优化呢?存在带$log$的算法么?
    考虑一下分治法

分治法

由主定理我们可以知道:$T(n)=2T(n/2)+O(n)\Rightarrow O(nlogn)$
这就需要我们尽可能的将原问题划分成2个相等的子问题
并且划分2个子问题,合并2个子问题,或者处理1个子问题对另1个子问题的影响不能超过$O(n)$

  • 划分
    如果将所有的点按照二维偏序(即横坐标$x$为第一关键字,纵坐标$y$为第二关键字)排序
    那么通过中间的那个点就可以将所有点划分成均等的2部分了
    这样我们以$O(nlogn)-O(1)$的时间复杂度做到了这一点

  • 递归处理子问题

    假设均等的2部分的子问题的答案分别是$d_1,d_2$,显然当前答案就是$d=min(d_1,d_2)$
    $(1)$类型的答案为$d$,但是我们发现$(2)$类型的答案很有可能$\le d$
    即中间那个点,在它两边的点形成的点对很有可能也会是答案
    也就说1个子问题对另1个子问题产生了影响,接下来思考如何计算这一部分的答案

  • 子问题间的影响

    • 可能产生影响的点
      对于中间点p来说,显然左右横坐标距离d以内的才是要考虑的点
      即若p点坐标为$(x,y)$,那么要考虑的点的横坐标$x-d<x’<x+d$,其它的点显然不能产生影响
      找到了这些可能产生影响的点后,点最坏有$n$个,如果一一枚举还是$O(n^2)$
      难道就逃脱不了$n^2$的命运了么?

    • 能对一个点贡献答案的点
      对于其中一个点$p_1$,能产生答案的点只考虑$y$比它大的那部分(这样一对点不会重复枚举)
      即若$p_1$点坐标为$(x,y)$,那么要考虑的点的横坐标$x-d<x’<x+d$,纵坐标$y \le y’ \le y +d$
      也就是说对$p_1$贡献答案的点应该就是如图那样的矩形部分

    • 矩形内至多有6个点
      我说矩形里至多有6个点你信不信!我们来证明一下:

      将矩形$R$的长为$2d$的边三等分,宽为$d$的边二等分
      这样我们得到了6个$\frac{2d}{3}\times \frac{d}{2}$的小矩形
      假设位于中轴线两侧的4个小矩形中有多于2个点,
      设$u,v$是位于同一小矩形中的两个点,则
      $d(u,v)=\sqrt{(x_u - x_v) ^ 2 + (y_u-y_v) ^ 2 }\le \sqrt{(d / 2) ^ 2 + (2d / 3) ^ 2} = \sqrt{25 / 36 * d ^ 2}=\frac{5d}{6} < d$
      因为递归已经算出两边子问题解为最优为$d$了,这显然是矛盾的,所以每个小矩形最多只能有1个点
      但是跨越中轴线的2个小矩形中可能会有多于2个点,但我们发现它们只能在中轴线上
      不然就与其他4个小矩形中的点构成了小于$d$的点对了,但是由于合法性最坏的点对如下图:

      这样最多就只有6个点了,重合点是非法的,因为会被分到2边,然后违法了$d$是最优解的条件
      $\blacksquare$

    • 时间复杂度分析
      有一个对$y$坐标排序,我们可以通过归并来实现,这样就还是$O(n)$
      总时间复杂度:$T(n)=2T(n/2)+O(6n)\Rightarrow O(nlogn)$

分治法实现

$UVA 10245 模版裸题:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//
// Created by TaoSama on 2016-03-18
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e4 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n;
typedef pair<double, double> P;
P a[N];
double dfs(int l, int r) {
if(l == r) return INF;
int m = l + r >> 1;
double x = a[m].first;
double d = min(dfs(l, m), dfs(m + 1, r));
inplace_merge(a + l, a + m + 1, a + r + 1, [](P x, P y) {
return x.second < y.second; //按照y来归并2个数组
});
vector<int> v;
for(int i = l; i <= r; ++i) {
if(abs(a[i].first - x) >= d) continue; //距离中轴小于d点加入
for(int j = 0; j < v.size(); ++j) {
int k = v[v.size() - 1 - j]; //倒着检查y坐标相差小于d的点
double dy = a[i].second - a[k].second;
if(dy >= d) break;
double dx = a[i].first - a[k].first;
d = min(d, hypot(dx, dy));
}
v.push_back(i);
}
return d;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d", &n) == 1 && n) {
for(int i = 1; i <= n; ++i) scanf("%lf%lf", &a[i].first, &a[i].second);
sort(a + 1, a + 1 + n);
double d = dfs(1, n);
if(d >= 1e4) {puts("INFINITY"); continue;}
printf("%.4f\n", d);
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到