最接近点对问题1
需积分: 0 84 浏览量
2022-08-03
16:04:30
上传
评论
收藏 459KB PDF 举报
最接近点对问题
给定平面上n个点的集合S，找其中的一对点，使得在n个点组
成的所有点对中，该点对间的距离最小。
◆为了使问题易于理解和分析，先来考虑一维的情形。此时，
S中的n个点退化为x轴上的n个实数 x1,x2,…,xn。最接近点
对即为这n个实数中相差最小的2个实数。
➢假设我们用x轴上某个点m将S划分为2个子集S1和S2 ，基
于平衡子问题的思想，用S中各点坐标的中位数来作分割点。
➢递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并
设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，
或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。
➢能否在线性时间内找到p3,q3？
评论0