0

当使用下面概述的扫描算法确定平面中最近的一对顶点时，是否可以在不进行额外运行的情况下确定多对顶点？

  1. 根据 x 坐标对点进行排序。
  2. 通过垂直线 x=xmid 将点集分成两个大小相等的子集。在左右子集中递归求解问题。这分别产生左侧和右侧最小距离 dLmin 和 dRmin。
  3. 在一组点对中找到最小距离 dLRmin，其中一个点位于分界线的左侧，另一点位于右侧。
  4. 最终答案是 dLmin、dRmin 和 dLRmin 中的最小值。
4

2 回答 2

0

在我看来，当你在一半中找到一对点的最小距离时，你可以记录最小距离的对。如果您找到其他具有相同距离的对，您可以通过将它们推入某种集合来记住所有它们。对左右两半以及中间检查的条子执行此操作，您应该能够打印出与最小距离相对应的任何列表的所有记录元素。就像是：

AllPairsMinDist(points[1...n])
    sort points according to x coordinate
    return AllPairsMinDistInternal(points[1...n])

AllPairsMinDistInternal(points[1...n])
    if n = 1 then
        return (+infinity, [])
    else if n = 2 then
        d = distance(points[1], points[2])
        c = (points[1], points[2])
        return (d, c)
    else then
        (dL, cL) = AllPairsMinDistInternal(points[1...floor(n/2)])
        (dR, cR) = AllPairsMinDistInternal(points[floor(n/2)+1...n])
        (dM, cM) = PairsMinDistMiddle(points[1...n], dL, dR)
        dMin = min(dL, dR, dM)
        cMin = []
        if dL = dMin then cMin = cMin union cL
        if dR = dMin then cMin = cMin union cR
        if dM = dMin then cMin = cMin union cM
        return (dMin, cMin)

AllPairsMinDistMiddle(points[1...n], dL, dR)
    if n = 1 then
        return (+infinity, [])
    else if n = 2 then
        d = distance(points[1], points[2])
        c = (points[1], points[2])
        return (d, c)
    else then
        xV = (points[floor(n/2)].x + points[floor(n/2)+1].x) / 2

        minD = min(dL, dR)
        minC = []

        ll = binary search for index of point with smallest
             x coordinate satisfying xV - x <= minD

        rr = binary search for index of point with largest
             x coordinate satisfying x - xV <= minD

        for i = ll to floor(n/2) do
            for j = floor(n/2) + 1 to rr do
                d = distance(points[i], points[j])
                if d = minD then
                    minC = minC union [(points[i], points[j])]
                else if d < minD then
                    minD = d
                    minC = [(points[i], points[j])]

        alternative to for loop:
            (dMin, cMin) = AllPairsMinDistInternal(points[ll...rr])

        return (dMin, cMin)

以上可能存在一些问题-我只是临时将其键入并且没有真正理解正在使用的算法-但是从您的高级描述来看，这听起来是可行的。

于 2017-11-13T14:33:51.380 回答
0

您需要将相等的最近对存储在单独的列表中。

每当您比较两个距离时，您必须将最短的距离与单独列表中的距离进行比较。

如果更短，则清空列表。

如果相等，则追加到列表中（可能是两对）。

使用恒定时间存储，这不会降低算法的复杂性。

于 2017-11-13T15:14:22.850 回答