第八章 数论算法及计算几何算法.ppt

由d的意义可知矩形R中任何两个S中的点的距离都大于等于d由此可知至少可以将d2d的矩形R分割成如图8-7所示的六部分其中任何一部分包含P2中的点最多有一个 因此在矩形R中最多只有6个P2中的点与p构成最接近点对 思考针对P1中的任意一点p检查P2中的哪6个点从而可以找出最接近点对呢 可以将p和P2中所有点到垂直线l上由于能与p点一起构成最接近点对候选者的P2中的点一定在矩形R中所以它们在直线l上的