10

假设如果 x1 ≤ x2 且 y1 ≤ y2，坐标 (x1,y1) 处的点支配另一点 (x2,y2)；

我有一组点 (x1,y1) , ....(xn,yn) 我想找到支配对的总数。我可以通过将所有点相互比较来使用蛮力来做到这一点，但这需要时间 O(n 2 )。相反，我想使用分而治之的方法在 O(n log n) 时间内解决这个问题。

现在，我有以下算法：

  • 画一条垂直线，将点集分成两个相等的 P left和 P right子集。作为基本情况，如果只剩下两点，我可以直接比较它们。

  • 递归计算 P left和 P right中的支配对数

  • 一些征服步骤？

问题是我看不到“征服”步骤应该在这里。我想计算从 P left到 P right的交叉点有多少对，但如果不比较两个部分中的所有点，我不知道该怎么做，这需要时间 O(n 2 )。

谁能给我一个关于如何进行征服步骤的提示？ 这是我的例子

所以 y 坐标的两半是：{1,3,4,5,5} 和 {5,8,9,10,12}

我画了分割线。

4

3 回答 3

8

假设您按 y 坐标按升序分别对两半中的点进行排序。现在，查看两半中 y 值最低的点。如果左侧最低点的 y 值低于右侧最低点，则该点受右侧所有点的支配。否则，右边的底点不会支配左边的任何东西。

在任何一种情况下，您都可以从两半中的一个中删除一个点，然后对剩余的排序列表重复该过程。这对每个点做了 O(1) 的工作，所以如果总共有 n 个点，这会做 O(n) 的工作（在排序之后）来计算两半中支配对的数量。如果您以前见过它，这类似于计算数组中的倒数的算法）。

考虑到排序点所需的时间 (O(n log n))，这个征服步骤需要 O(n log n) 时间，给出递归

T(n) = 2T(n / 2) + O(n log n)

根据主定理，这解决了 O(n log 2 n) 。

但是，您可以加快速度。假设在你开始分治步骤之前，你通过它们的 y 坐标对点进行预排序，做一次 O(n log n) 的工作。使用类似于最接近点对问题的技巧，您可以在每个大小为 n 的子问题上以 O(n) 时间对每一半中的点进行排序（有关详细信息，请参阅本页底部的讨论）。这将复发更改为

T(n) = 2T(n / 2) + O(n)

根据需要，它解决了 O(n log n)。

希望这可以帮助！

于 2013-10-22T06:56:22.793 回答
1

那么通过这种方式你有 O(n^2) 只是为了划分子集......
我的方法会有所不同

  1. 按 X ... O(n.log(n)) 对点进行排序
  2. 现在检查 Y
    • 但仅检查具有较大 X 的点（如果您对它们进行升序排序，则使用较大的索引）
  3. 所以现在你有 O(n.log(n)+(nn/2))

您还可以通过单独进行 X 和 Y 测试来进一步加快速度，然后结合结果，这将导致 O(n + 3.n.log(n))

  1. 将索引属性添加到您的点
    • 其中 index = 0xYYYYXXXXh 是无符号整数类型
    • YYYY 是 Y 排序数组中点的索引
    • XXXX 是 X 排序数组中点的索引
    • 如果您有超过 2^16 个点，请使用大于 32 位的数据类型。
  2. 通过升序 X 对点进行排序并设置其索引的 XXXX 部分 O1(n.log(n))
  3. 通过升序 Y 对点进行排序并设置其索引的 YYYY 部分 O2(n.log(n))
  4. 按升序对点进行排序 O3(n.log(n))
  5. 现在点 i 支配任何点 j 如果 (i < j)
    • 但是如果您需要为任何点创建实际上所有的对
    • 这需要 O4(nn/2) 所以这种方法不会节省一点时间
    • 如果您在任何点只需要一对，那么简单的循环就足够了 O4(n-1)
    • 所以在这种情况下 O(n-1+3.n.log(n)) -> ~O(n+3.n.log(n))

希望它有所帮助，...当然，如果您坚持使用这种细分方法，那么我没有更好的解决方案适合您。

PS。为此，您不需要任何额外的递归，只需 3x 排序，任何点都只需要一个 uint，因此内存需求不是那么大，甚至应该比递归调用一般的细分递归更快

于 2013-10-22T07:23:13.803 回答
0

该算法在O(N*log(N))中运行，其中 N 是点列表的大小，它使用O(1)额外空间。

执行以下步骤：

  1. 按 y 坐标（升序）对点列表进行排序，按 x 坐标（升序）打破平局。
  2. 以相反的顺序遍历排序列表以计算支配点：如果当前 x 坐标 >= 到目前为止遇到的最大 x 坐标值，则增加结果并更新最大值。

这是有效的，因为您确定如果所有具有较大 y 坐标的对的 x 坐标都小于当前点，则您已经找到了一个支配点。排序步骤使其非常高效。

这是Python代码：

def my_cmp(p1, p2):
    delta_y = p1[1] - p2[1]
    if delta_y != 0:
        return delta_y
    return p1[0] - p2[0]

def count_dom_points(points):
    points.sort(cmp = my_cmp)
    maxi = float('-inf')
    count = 0
    for x, y in reversed(points):
        if x >= maxi:
        count += 1
        maxi = x

    return count
于 2016-10-27T10:16:30.703 回答