分治法Finding the Closet Pair of Points.pdf

分治法例：寻找最近点对 （Finding the Closet Pair of Points ） 问题：给定平面上的n 个点，要找出距离最近的两个点。 Brute-force 法：把Cn2 个点对的距离逐一计算一遍， 在计算过程中纪录下：到目前为止距离最近的点对。 这样，当所有的点对都被检查过之后，答案也就得到了。 但算法的时间复杂度为Θ(n2), ∵点对共有Cn2=n(n-1)/2 个。 能否使用分治法？如何使用分治法？ 找一条垂直线把平面分成两部分， 使得线左边和线右边的点的数目基本相等。 怎样才能