1.3. 分治法—最近点对问题

1. 问题描述

给定平面S上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小

2. 求解过程

• 划分：将集合S分成两个大小基本相等的子集 S 1 S_1 S1​和 S 2 S_2 S2​
• 求解子问题：递归地求解两个子问题
• 合并问题的解（三种情况）
  • 组成S的最近点对的2个点都在 S 1 S_1 S1​中
  • 组成S的最近点对的2个点都在 S 2 S_2 S2​中
  • 组成S的最近点对的2个点分别在 S 1 S_1 S1​和 S 2 S_2 S2​中

3. 算法思路

• 预排序：把S中的点分别按x坐标值和y坐标值排序
• 如果S中包含的点少于4个，则采用蛮力法直接求解
• 划分
  • 计算S中各点x坐标的中位数m
  • 用垂线L:x=m把S划分成两个大小相等的子集合 S 1 S_1 S1​和 S 2 S_2 S2​， S 1 S_1 S1​中的点在L左边， S 2 S_2 S2​中的点在L右边
    
• 求解子问题：递归地在 S 1 S_1 S1​和 S 2 S_2 S2​中找出最近点对( p 1 p_1 p1​, p 2 p_2 p2​)和( q 1 q_1 q1​, q 2 q_2 q2​)，设其距离分别为 d 1 d_1 d1​和 d 2 d_2 d2​
• 合并解
  

4. (p,q)的搜索方法

1. 搜索范围缩小到以L为中心、宽度为2d的临界区内
   

2. 对于点 p ∈ P p \in P p∈P，需要考察Q中的各个点和点p之间的距离是否小于d，显然，Q中这样点的y轴坐标一定位于区间[y-d, y+d]之间，即这样的点一定落在一个 d × 2 d d \times 2d d×2d的矩形区域内。而且，根据鸽舍原理可知这样的点不会超过6个
   
   

3. 临界区内所有点集构成点集Ｒ，将其按照y坐标排序，对Ｒ中的每个点 r i r_i ri​依次考察其后的点 r j r_j rj​（最多只要观察紧随其后的7个点），因此，合并步骤可以在线性时间内完成
   

5. 算法伪码

6. 算法代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h> 
//平面点的结构体定义
typedef struct point {
	double x;
	double y;
} point;
//x坐标的比较函数
int compare_x(const void* _a, const void* _b) {
	point* a = (point*)_a;
	point* b = (point*)_b;
	return a->x - b->x;
}
//y坐标的比较函数
int compare_y(const void* _a, const void* _b) {
	point* a = (point*)_a;
	point* b = (point*)_b;
	return a->y - b->y;
}

//计算两点间距离
double distance(point i, point j) {
	return sqrt(pow(i.x - j.x, 2) + pow(j.y - i.y, 2));
}
//求解最近点对
double closestPoints(point* points, int start, int end) {
	double d = INT_MAX;
	//若点集合为空，则直接返回INT_MAX
	if (start == end) {
		return d;
	}
	//若有一个点，则直接计算两点距离
	if (start + 1 == end) {
		return distance(points[start], points[end]);
	}
	//计算中间点
	int mid = (start + end) / 2;
	//递归求解子问题1
	double d1 = closestPoints(points, start, mid);
	//递归求解子问题2
	double d2 = closestPoints(points, mid + 1, end);
	d = fmin(d1, d2);
	point *R = (point*)malloc(sizeof(point)*(end - start + 1));
	int top = 0;
	//构造临界区集合R
	for (int i = start; i <= end; ++i) {
		if (fabs(points[i].x - points[mid].x) < d) {
			R[top++] = points[i];
		}
	}
	//将集合R中的点按y坐标进行快速排序
	/* qsort()函数是C库中实现的快速排序函数
		void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
		void *base：待排序数组的起始地址
		size_t nitems：待排序数组的元素个数
		size_t size：元素所占的字节数
		int (*compar)(const void *, const void*)：比较函数
	*/
	qsort(R, top, sizeof(point), compare_y);
	for (int i = 0; i < top - 1; ++i) {
		for (int j = i + 1; j < top; ++j) {
			if (fabs(points[i].y - points[j].y) < d) {
				double d3 = distance(points[i], points[j]);
				if (d3 < d) {
					d = d3;
				}
			}
		}
	}
	return d;
}

int main() {
	int n;
	printf("请输入点的数量：");
	scanf_s("%d", &n);
	point *points = (point *)malloc(sizeof(point) * n);
	for (int i = 0; i < n; i++) {
		points[i].x = (double)(rand() % 10000)/100 - 50;						//横坐标范围 -50~49
		points[i].y = (double)(rand() % 10000)/100 - 50;						//纵坐标范围 -50~49
		printf("S[%d]=(%lf, %lf)\n", i, points[i].x, points[i].y);
	}
	qsort(points, n, sizeof(point), compare_x);
	printf("最小的距离为%lf", closestPoints(points, 0, n - 1));
	return 0;
}

7. 时间复杂度